백준 문제풀이 - 너비 우선 탐색 - 1021번

BFS 알고리즘 분류에 있던 문제로 너비 우선 탐색으로 해결한 문제이다. 

문제는 최소한의 배추흰지렁이를 필요로 하기에 연속되어 있는 1의 영역의 개수를 구하는 문제이다. 

영역의 개수를 구하는 문제이기에 너비 우선 탐색을 이용하여 인접한 칸에서 배추가 있는 칸으로 이동하고 모든 배추를 세었을 때 다시 한번 너비 우선 탐색을 반복한다. 

---

1. 입력에서 주어지는 정보를 받는 변수를 선언한다. 추가적으로 배추칸을 탐색했는지 여부를 확인하기 위한 visited 배열을 생성한다. 

2. 여기서 추가적으로 좌표를 이동하며 인접한 칸의 값을 탐색하기 위해 dx, dy 배열을 생성한다. 

3. 배열을 입력받기 이전에 input 배열과 visited 배열에 값을 초기화해준다.
    (for 문을 이용하여 input 배열은 0 , visited 배열은 false 값을 채운다.)

4. 이후 배추가 있는 칸의 위치를 입력받으며 해당 칸의 값은 1로 변경한 후 반복문을 돌리며 방문 안한 칸이며 해당 칸의 값이 1이면 BFS 알고리즘을 실행한다. 

5. BFS 알고리즘은 큐를 사용한 알고리즘이다.
  1) 4번에 해당하는 인덱스 위치 값을 큐에 넣는다. 
  2) visited 배열의 인덱스 값을 true 로 변경한다. 
  3) 큐가 종료될 때까지 while 반복문을 실행한다. - 가장 앞의 값을 빼면서 진행하기 때문
  4) while문 - 큐의 맨 앞 인덱스 값을 now 값으로 저장
       while문 - 인접한 칸의 배추를 확인하기 dx, dy 값을 이용하여 상하좌우를 확인함
       while문 - 상하좌우의 인덱스값이 input 배열의 크기 맞도록 조건 설정 + 해당 칸의 방문 상태가 false 이면서 input 값이 1 인 조건
       while문 - 해당 조건에 부합한다면 visit 의 인덱스에 해당하는 값을 true 값으로 변경 + 큐에 상하좌우 중에 해당 되는 인덱스값 추가
  5) while 문이 종료 된 후 최종 count 값을 증가시켜준다. 

 

정답코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class No_1012 {
    static int re;
    static int n;
    static int m;
    static int inCnt;
    static int input[][];
    static Boolean visit[][];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        re = sc.nextInt();
        for (int i = 0; i < re; i++) {

            m = sc.nextInt(); // row
            n = sc.nextInt(); // column
            input = new int[m][n];
            visit = new Boolean[m][n];
            cnt = 0;

            inCnt = sc.nextInt();

            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    input[j][l] = 0;
                    visit[j][l] = false;
                }
            }

            for (int j = 0; j < inCnt; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                input[x][y] = 1;
            }
            //--배열 완성
            // x 값 마지노선 m y 값 마지노선 n


            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (!visit[j][l] && input[j][l] == 1) {
                        BFS(j, l);
                    }
                }
            }
            System.out.println(cnt);
        }

    }

    private static void BFS(int mx, int my) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{mx, my});
        visit[mx][my] = true;
        while (!queue.isEmpty()) { 
            int now[] = queue.poll();

            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < m && y < n) {
                    if (!visit[x][y] && input[x][y] == 1) {
                        visit[x][y] = true;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        cnt++;
    }
}