자바(백준) 1012 유기농 배추

import java.io.*;
import java.util.*;
 
public class Main {
    static int M,N,K; // M : 가로길이 N : 세로길이 K : 배추 갯수
    static boolean[][] visit;
    static int ad[][];
    static Queue<Integer> Q;
    public static void main(String []args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            int test = Integer.parseInt(st.nextToken());    //테스트 갯수
 
            for(int i = 0; i < test; i++){
                int warm = 0;
                st = new StringTokenizer(br.readLine());
                M = Integer.parseInt(st.nextToken());
                N = Integer.parseInt(st.nextToken());
                K = Integer.parseInt(st.nextToken());
                ad = new int[M][N];
                visit = new boolean[M][N];
                for(int j = 0; j < K; j++){
                    st = new StringTokenizer(br.readLine());
                    int t1 = Integer.parseInt(st.nextToken());
                    int t2 = Integer.parseInt(st.nextToken());
                    ad[t1][t2] = 1;
                }
                for(int m = 0; m < M; m++){
                    for(int n = 0; n < N; n++){
                        if(!visit[m][n] && ad[m][n] == 1){
                            bfs(m,n);
                            warm++;
                        }
                    }
                }
                System.out.println(warm);
            }
 
        }
 
        public static void bfs(int x, int y){
            Q = new LinkedList<>();
            int dx[] = {0,0,1,-1};
            int dy[] = {-1,1,0,0};
            Q.add(x);
            Q.add(y);
            while(!Q.isEmpty()) {
                int X = Q.poll();   //틀린부분 int row = Q.poll() + dx[i] 라 해서 틀림
                int Y = Q.poll();   //틀린부분
                for (int i = 0; i < 4; i++) {
                    int row = X + dx[i];
                    int col = Y + dy[i];
                    if (isRangeTrue(row, col) && !visit[row][col] && ad[row][col] == 1) {
                        visit[row][col] = true;
                        Q.add(row);
                        Q.add(col);
                    }
                }
            }
        }
 
        public static boolean isRangeTrue(int x, int y){
            return x >= 0 && x < M && y >= 0 && y < N;
        }
}
 
 
 

 

이 문제를 BFS로 처음 풀었을 때, 주석 부분을 보다시피, 왜 꼭 저기에 X와 Y 변수를 설정해줘서 그곳에 Q의 값을 저장해줘야 하는지를 몰랐다. 그러나 생각해보니까 만약 int row = Q.poll() + dx[i] 를 해주면 내가 Q.add한 row, col값을 계속해서 빼내기 때문에 다른 곳을 탐색하게 된다. 다시 말하면, 1,1에서 동서남북으로 이동해야 하는 것을, 나는 1,1 동쪽 갔다가 row,col 부터 다시 시작해서 또 동서남북을 탐색하려 하고 이런 식으로 코드가 진행이 된다. 그래서 잘못된 코드임을 깨달았다.

 

또한, 처음에는 DFS로 푸는 것은 쉽게 풀었는데, BFS로는 어떻게 풀어야하지해서 구글링을 했다. 그러나 Queue<E> 에서 E에 int[] 를 집어넣는 것도 많고, 뭐 상당하게 복잡한 것들이 있었다. 그러나 큐의 성질을 이용하여 x좌표를 먼저 넣어서 x좌표를 먼저 꺼낼 수 있기 때문에 차례대로 집어넣고 빼면 될 것 같다는 생각이 들었다. 그래서 E에 다른 걸 집어넣을 필요 없이 Integer로 선언하고 문제를 풀었다.