#유형 : 그래프, BFS

# BFS의 기본 문제중 한 가지. 기존의 다른 탐색문제에서 나이트의 이동 범위만 수정해주면 해결할 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p7562 {
    static int moveX[] = {1,2,2,1,-1,-2,-2,-1};
    static int moveY[] = {-2,-1,1,2,2,1,-1,-2};
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int t=0; t<tc; t++) {
            int n = Integer.parseInt(br.readLine());
            int arr[][] = new int[n][n];
            int currentX, currentY, targetX, targetY;
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            currentX = Integer.parseInt(st.nextToken());
            currentY = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            targetX = Integer.parseInt(st.nextToken());
            targetY = Integer.parseInt(st.nextToken());
            
            Point start = new Point(currentX,currentY);
            Point target = new Point(targetX, targetY);
            
            bfs(start, target, arr);
        }
    }
 
    private static void bfs(Point start, Point target, int[][] arr) {
        // TODO Auto-generated method stub
        Queue<Point> queue =new LinkedList<Point>();
        queue.add(start);
        boolean visit[][] = new boolean[arr.length][arr.length];
        visit[start.y][start.x] = true;
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            if(p.y==target.y && p.x==target.x) {
                System.out.println(arr[p.y][p.x]);
                return;
            }
            
            for(int d=0; d<8; d++) {
                int newY = p.y + moveY[d];
                int newX = p.x + moveX[d];
                if(0<=newX && newX<arr.length && 0<=newY && newY<arr.length && !visit[newY][newX]) {
                    visit[newY][newX] = true;
                    arr[newY][newX] = arr[p.y][p.x] + 1;
                    queue.add(new Point(newX,newY));
                }
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_10026 적록색약 - Java 자바  (0) 2020.02.13
#백준_1325 효율적인 해킹 - Java 자바  (0) 2020.02.12
#백준_2573 빙산 - Java 자바  (0) 2020.02.10
#백준_1062 가르침 - Java 자바  (0) 2020.02.10
#백준_7569 토마토 - Java 자바  (0) 2020.02.09

# 유형 : BFS

# 빙산 녹는 처리를 해주는 BFS, 연결성 체크를 위한 BFS  2가지를 구현하면 된다. 백준 7569, 3055 문제도 탐색을 두번하는 문제였는데, 풀어봤다면 어떻게 접근할지 보이는 문제라고 생각한다. 

 

# 구현

1. 빙산인 부분을 리스트에 저장

2. 리스트에 저장된 빙산의 좌표를 큐에 넣고, 큐의 사이즈 만큼 좌표의 4방향중 0인 곳인 만큼 값을 빼준다. 

3. 값을 빼주는 작업이 끝날 때마다 연결성을 체크하여 2개이상으로 분리되는지 체크한다.

4. 빙산이 다 녹을때까지 분리가 안된다면 0을 출력한다.

5. 예외케이스로 입력부터 두 개이상으로 분리되는 경우가 있다. 이를 처리해줘야 한다.

 

추가적인 테스트케이스

https://www.acmicpc.net/board/view/19033

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2573 {
    static int result=0;
    static int N,M;
    static int arr[][],map[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static ArrayList<Point> arrList = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        map = new int[N][M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                int val = Integer.parseInt(st.nextToken());
                arr[i][j] = val;
                map[i][j] = val;
                if(val != 0)
                    arrList.add(new Point(j,i));
            }
        }
        if(check(arrList.get(0)) != arrList.size())
            System.out.println(0);
        else
            bfs();
    }
    
    public static void bfs() {
        Queue<Point> queue = new LinkedList<Point>();
        
        for(int k=0; k<arrList.size(); k++) {
            Point p = arrList.get(k);
            queue.add(p);
        }
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            result++;
            for(int s=0; s<size; s++) {
                Point p = queue.poll();
                int count = 0;
                for(int d=0; d<4; d++) {
                    int newX = p.x + moveX[d];
                    int newY = p.y + moveY[d];
                    if(0<=newX && newX<M && 0<=newY && newY<N && arr[newY][newX]==0)
                        count++;
                }
                if(count >= map[p.y][p.x])
                    map[p.y][p.x] = 0;
                else {
                    map[p.y][p.x]-=count;
                    queue.add(p);
                }
            }
            for(int q=0; q<N; q++) {
                for(int w=0; w<M; w++) {
                    arr[q][w] = map[q][w];
                }
            }
            if(queue.peek()!=null && check(queue.peek()) != queue.size()) {
                System.out.println(result);
                return;
            }
        }
        System.out.println(0);
    }
    
    //연결 체크
    public static int check(Point p) {
        int count = 0;
        boolean visit[][] = new boolean[N][M];
        Queue<Point> queue = new LinkedList<>();
        queue.add(p);
        visit[p.y][p.x] = true;
        while(!queue.isEmpty()) {
            Point tmp = queue.poll();
            count++;
            for(int d=0; d<4; d++) {
                int newY = tmp.y + moveY[d];
                int newX = tmp.x + moveX[d];
                if(0<=newY && newY<N && 0<=newX && newX<M ) {
                    if(arr[newY][newX]!=0 && !visit[newY][newX]) {
                        visit[newY][newX]=true;
                        queue.add(new Point(newX,newY));
                    }
                }
            }
        }
        return count;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1325 효율적인 해킹 - Java 자바  (0) 2020.02.12
#백준_7562 나이트의 이동 - Java 자바  (0) 2020.02.11
#백준_1062 가르침 - Java 자바  (0) 2020.02.10
#백준_7569 토마토 - Java 자바  (0) 2020.02.09
#백준_14503 로봇 청소기 - Java 자바  (0) 2020.02.09

# 유형 : 탐색, 브루트포스, dfs, 문자열, 시뮬레이션

# 문제를 이해하는게 참 어려웠다..

# 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 에서 우선 5개의 알파벳을 사용한다. 따라서 K가 5 보다 작은 값이 들어온다면 읽을 수 없다. 그리고 K가 26이라면 모든 단어를 읽을 수 있다.

만약 K가 6이라면,  a,n,t,i,c 5개를 제외한 알파벳 21개의 알파벳 중 1개를 배웠을 때 주어진 문자열을 읽을 수 있는 최대 경우의 수를 구하는 문제이다. 따라서 백트래킹을 이용하여 탐색하는 방식으로 문제를 접근한다면 어렵지 않게 해결할 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1062 {
    static int N,K;
    static int max = 0;
    static boolean visit[] = new boolean[26];
    static String[] stArr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        stArr = new String[N];
        //남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.  a n t i c
        if(K<5) {
            System.out.println(0);
            return;
        }else if(K==26) { 
            System.out.println(N);
            return;
        }else {
            for(int n=0; n<N; n++) {
                String str = br.readLine();
                stArr[n] = str.substring(4, str.length()-4);
            }
            K-=5;
            visit['a'-97]=true;
            visit['n'-97]=true;
            visit['t'-97]=true;
            visit['i'-97]=true;
            visit['c'-97]=true;
            dfs(0, 0);
            System.out.println(max);
        }
        
    }
    private static void dfs(int start, int count) {
        // TODO Auto-generated method stub
        if(count == K) {
            int rs = 0;
            for(int i=0; i<N; i++) {
                boolean isTrue = true;
                for(int j=0; j<stArr[i].length(); j++) {
                    if(!visit[stArr[i].charAt(j)-97]) {
                        isTrue = false;
                        break;
                    }
                }
                if(isTrue) {
                    rs++;
                }
            }
            max = Math.max(max, rs);
            return;
        }
        
        for(int i=start; i<26; i++) {
            if(!visit[i]) {
                visit[i]=true;
                dfs(i, count+1);
                visit[i]=false;
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_7562 나이트의 이동 - Java 자바  (0) 2020.02.11
#백준_2573 빙산 - Java 자바  (0) 2020.02.10
#백준_7569 토마토 - Java 자바  (0) 2020.02.09
#백준_14503 로봇 청소기 - Java 자바  (0) 2020.02.09
#백준_2206 벽 부수고 이동하기 - Java 자바  (0) 2020.02.08

# 유형 : 탐색, BFS

# 3055번 문제 고슴도치에서 차원이 한개 늘어난 문제. https://www.acmicpc.net/problem/3055

3055번 문제를 먼저 풀어보고 푼 다면 어렵지 않게 풀수있다. 차원1개가 늘어나고, 그 차원만큼 방향도 2개 증가해서 그것에 대한 방향과 조건들을 추가해주면 된다. 시간 내로 푸는 연습을 하느라, 코드는 깔끔하지 않다.

 

3055번: 탈출

문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p7569 {
    static int zero=0;
    static int cnt=0;
    static int M,N,H;
    static int arr[][][], map[][][];
    static int moveX[] = {0,1,0,-1,0,0};
    static int moveY[] = {-1,0,1,0,0,0};
    static int moveH[] = {0,0,0,0,1,-1};
    static ArrayList<Po> arrList = new ArrayList<>();
    static Queue<Po> tomato = new LinkedList<Po>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        
        arr = new int[N][M][H];
        map = new int[N][M][H];
        
        for(int h=0; h<H; h++) {
            for(int n=0; n<N; n++) {
                st = new StringTokenizer(br.readLine());
                for(int m=0; m<M; m++) {
                    int val = Integer.parseInt(st.nextToken());
                    if(val == 1) {
                        tomato.add(new Po(m,n,h));
                        arrList.add(new Po(m,n,h));
                    }
                    arr[n][m][h] = val;
                }
            }
        }
        bfs();
        for(int h=0; h<H; h++) {
            for(int n=0; n<N; n++) {
                for(int m=0; m<M; m++) {
                    if(arr[n][m][h]==0)
                        zero++;
                }
            }
        }
        if(cnt==1 && zero>0) {
            System.out.println("0");
        }else if(zero == 0 && cnt>0) {
            System.out.println(cnt-1);
        }else {
            System.out.println("-1");
        }
    }
    
    public static class Po{
        int x;
        int y;
        int h;
        public Po(int x,int y,int h) {
            this.x=x;
            this.y=y;
            this.h=h;
        }
    }
    
    public static void bfs() {
        Queue<Po> queue = new LinkedList<>();
        for(int i=0; i<arrList.size(); i++) {
            Po p = arrList.get(i);
            map[p.y][p.x][p.h] = 1;
            queue.add(new Po(p.x, p.y, p.h));
        }
        while(!queue.isEmpty()) {
            int current = tomato.size();
            for(int i=0; i<current; i++) {
                Po p = tomato.poll();
                int currentX = p.x;
                int currentY = p.y;
                int currentH = p.h;
                
                for(int d=0; d<6; d++) {
                    int newX = currentX + moveX[d];
                    int newY = currentY + moveY[d];
                    int newH = currentH + moveH[d];
                    
                    
                    if(0<=newX && newX<M && 0<=newY && newY<N && 0<=newH && newH<H) {
                        if(arr[newY][newX][newH] == 0) {
                            arr[newY][newX][newH] = 1;
                            tomato.add(new Po(newX, newY, newH));
                        }
                    }
                }
                
            }
            current = queue.size();
            for(int i=0; i<current; i++) {
                Po p = queue.poll();
                int x = p.x;
                int y = p.y;
                int h = p.h;
                
                for(int d=0; d<6; d++) {
                    int newX = x + moveX[d];
                    int newY = y + moveY[d];
                    int newH = h + moveH[d];
                    if(0<=newX && newX<M && 0<=newY && newY<N && 0<=newH && newH<H) {
                        if(arr[newY][newX][newH]==1 && arr[newY][newX][newH]!=-1 && map[newY][newX][newH]==0) {
                                map[newY][newX][newH] = map[y][x][h] + 1;
                                queue.add(new Po(newX,newY,newH));
                        }
                    }
                }
            }
            cnt++;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2573 빙산 - Java 자바  (0) 2020.02.10
#백준_1062 가르침 - Java 자바  (0) 2020.02.10
#백준_14503 로봇 청소기 - Java 자바  (0) 2020.02.09
#백준_2206 벽 부수고 이동하기 - Java 자바  (0) 2020.02.08
#백준_1012 유기농 배추 - Java 자바  (0) 2020.02.07

# 유형 : 시뮬레이션, 재귀

# 조건을 잘 확인하면서 구현하면 어렵지 않은 문제. 재귀 함수를 통해 탐색을 이어나가면서 만약 더이상 탐색을 할 곳이 없을때 뒤로 빠지는 것 까지 잘 생각하고 구현해주면 된다. 이 때 벽이 있는 예외처리를 잘 해줘야함.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p14503 {
    static int N,M,r,c,d;
    static int arr[][];
    static int rs=1;
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        
        
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                int val = Integer.parseInt(st.nextToken());
                if(val == 1)
                    val=-1;
                arr[i][j] = val;
            }
        }
        clean(r,c,d);
        System.out.println(rs);
    }
    
    public static void clean(int i, int j, int dir) {
        arr[i][j] = 1;
        
        for(int d=0; d<4; d++) {
            dir = (dir+3)%4;
            int newX = j + moveX[dir];
            int newY = i + moveY[dir];
            
            if(0<=newX && newX<M && 0<=newY && newY<N && arr[newY][newX]==0) {
                rs++;
                clean(newY, newX, dir);
                return;
            }
        }
        
        int back = (dir+2)%4;
        int backX = j + moveX[back];
        int backY = i + moveY[back];
        
        if(0<=backX && backX<M && 0<=backY && backY<N && arr[backY][backX]!=-1)
            clean(backY,backX,dir);
    }
    
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1062 가르침 - Java 자바  (0) 2020.02.10
#백준_7569 토마토 - Java 자바  (0) 2020.02.09
#백준_2206 벽 부수고 이동하기 - Java 자바  (0) 2020.02.08
#백준_1012 유기농 배추 - Java 자바  (0) 2020.02.07
#백준_11559 PuyoPuyo - Java 자바  (0) 2020.02.07

# 유형 : 탐색, BFS

# 기존 bfs에서 조금 더 복잡해진 문제. 따로 저장할까 생각하려다가 벽을 뚫었는지 아닌지 체크하기위해 배열을 3차원으로 선언하여 문제를 해결.

 

벽 부술 곳을 하나하나 체크하면 당연히.. 시간초과가 날 것

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2206 {
    static int N,M;
    static int arr[][], map[][][];
    static int moveX[] = {0,-1,0,1};
    static int moveY[] = {-1,0,1,0};
    static ArrayList<Point> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        map = new int[N][M][2];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                int val = str.charAt(j)-'0';
                arr[i][j] = val;
            }
        }
        
        System.out.println(bfs(0,0));
    }
    
    public static int bfs(int i, int j) {
        Queue<Po> queue = new LinkedList<>();
        queue.add(new Po(i,j,1));
        map[i][j][1]=1;
        
        while(!queue.isEmpty()) {
            Po p = queue.poll();
            
            if(p.x == M-1 && p.y == N-1)
                return map[p.y][p.x][p.is];
            
            for(int d=0; d<4; d++) {
                int newY = p.y + moveY[d];
                int newX = p.x + moveX[d];
                
                if(0<=newY && newY<N && 0<=newX && newX<M) {
                    if(arr[newY][newX] == 1 && p.is==1) {
                        map[newY][newX][p.is-1] = map[p.y][p.x][p.is]+1;
                        queue.add(new Po(newX,newY,p.is-1));
                    }
                    else if(arr[newY][newX] == 0 && map[newY][newX][p.is] == 0) {
                        map[newY][newX][p.is] = map[p.y][p.x][p.is] + 1;
                        queue.add(new Po(newX,newY,p.is));
                    }
                }
            }
        }
        return -1;
    }
    
    public static class Po{
        int x;
        int y;
        int is;
        public Po(int x,int y,int is) {
            this.x=x;
            this.y=y;
            this.is=is;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_7569 토마토 - Java 자바  (0) 2020.02.09
#백준_14503 로봇 청소기 - Java 자바  (0) 2020.02.09
#백준_1012 유기농 배추 - Java 자바  (0) 2020.02.07
#백준_11559 PuyoPuyo - Java 자바  (0) 2020.02.07
#백준_5397 키로거 - Java 자바  (0) 2020.02.06

# 유형 : 탐색(DFS,BFS)

# BFS를 통해 문제를 풀었다. 큐에 넣기전에 방문 체크를 해주고 넣어야 하는데 생각없이 큐에서 poll해서 방문 체크를 해줘서 계속 시간초과가 났다. 당연한 것인데 이것때문에 시간을 버렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1012 {
    static int M,N,K;
    static int arr[][];
    static boolean visit[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            
            arr = new int[N][M];
            visit = new boolean[N][M];
            int count = 0;
            for(int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
 
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr[y][x] = 1;
            }
            
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(arr[i][j] == 1 && !visit[i][j]) {
                        bfs(i,j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
    public static void bfs(int i, int j) {
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(j,i));
        visit[i][j] = true;
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            int y = p.y;
            int x = p.x;
        
            for(int d=0; d<4; d++) {
                int newY = y + moveY[d];
                int newX = x + moveX[d];
            
                if(0<=newY && newY<N && 0<=newX && newX<M) {
                    if(arr[newY][newX] == 1 && !visit[newY][newX]) {
                        visit[newY][newX] = true;
                        queue.add(new Point(newX,newY));
                    }
                }
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_14503 로봇 청소기 - Java 자바  (0) 2020.02.09
#백준_2206 벽 부수고 이동하기 - Java 자바  (0) 2020.02.08
#백준_11559 PuyoPuyo - Java 자바  (0) 2020.02.07
#백준_5397 키로거 - Java 자바  (0) 2020.02.06
#백준_1024 수열의 합 - Java 자바  (0) 2020.02.06

# 유형 : 탐색 + 시뮬레이션

# 조건문만 잘 따져서 구현하면 어렵지 않은 문제이다, 코드를 더 간결화 시킬 수 있을 것 같은데.. 귀찮다.

# 연결을 체크해주는 탐색 메소드 + 연결을 체크해주는 메소드를 통해 얻은 삭제할 대상을 삭제해주는 메소드 + 삭제하고 난 후 칸을 땡겨주는 메소드 3개를 구현하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class p11559 {
    
    static char arr[][] = new char[12][6];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static ArrayList<Point> deleteList;
    static boolean visit[][];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        int result=0;
        for(int i=0; i<12; i++) {
            str = br.readLine();
            for(int j=0; j<6; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        while(true) {
            deleteList = new ArrayList<>();
            visit = new boolean[12][6];
            
            for(int i=11; i>=0; i--) {
                for(int j=0; j<6; j++) {
                    if(arr[i][j] != '.' && !visit[i][j] && check(i,j) >= 4) {
                        deleteList.add(new Point(j,i));
                    }
                }
            }
            if(deleteList.size()==0)
                break;
            for(int i=0; i<deleteList.size(); i++) {
                delete(deleteList.get(i).y, deleteList.get(i).x);
            }
            process();
            result++;
            
        }
        
        System.out.println(result);
    }
    public static void process() {
        for(int i=10; i>=0; i--) {
            for(int j=0; j<6; j++) {
                int next=i;
                boolean isTrue=false;
                while(next<11 && arr[next+1][j] == '.') {
                    next++;
                    isTrue=true;
                }
                if(isTrue) {
                    char tmp = arr[i][j];
                    arr[next][j] = tmp;
                    arr[i][j] = '.';
                }
                
            }
        }
    }
    public static void delete(int i, int j) {
        char ch = arr[i][j];
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(j,i));
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            int y = p.y;
            int x = p.x;
            arr[y][x] = '.';
            for(int d=0; d<4; d++) {
                int newY = y + moveY[d];
                int newX = x + moveX[d];
                if(0<=newY && newY<12 && 0<=newX && newX<6 && arr[newY][newX]==ch) {
                    queue.add(new Point(newX,newY));
                }
            }
        }
    }
    
    public static int check(int i, int j) {
        char ch = arr[i][j];
        int rs=0;
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(j,i));
        while(!queue.isEmpty()) {
            
            Point p = queue.poll();
            visit[p.y][p.x] = true;
            rs++;
            
            for(int d=0; d<4; d++) {
                int newY = p.y + moveY[d];
                int newX = p.x + moveX[d];
                if(0<=newY && newY<12 && 0<=newX && newX<6 && !visit[newY][newX] && arr[newY][newX] == ch) {
                    queue.add(new Point(newX,newY));
                }
            }
        }
        return rs;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2206 벽 부수고 이동하기 - Java 자바  (0) 2020.02.08
#백준_1012 유기농 배추 - Java 자바  (0) 2020.02.07
#백준_5397 키로거 - Java 자바  (0) 2020.02.06
#백준_1024 수열의 합 - Java 자바  (0) 2020.02.06
#백준_1068 트리 - Java 자바  (0) 2020.02.05

+ Recent posts

티스토리툴바