[algorithm] BFS/DFS 백준1012 유기농배추

◾문제

유기농 배추

레벨: 실버2

유형: BFS/DFS

https://www.acmicpc.net/problem/1012

 

◾풀이

전형적인 BFS/DFS 문제이다. 본 글에서는 bfs를 이용하여 풀이하였다.

 

bfs 풀이가 어려운 분들을 위해 자세히 설명하려고 하였는데, 이해가 안 가는 부분이 있다면 댓글로 알려주세요

 

 

문제이해

배추는 상하좌우로 인접해 있고, 배추가 인접한 곳에서는 지렁이는 1마리만 필요하다.  즉 떨어져있는 배추들의 묶음이 전체에서 몇 개인지 세면 그것이 곧 필요한 지렁이의 개수가 된다.  

 

배추 밭

배추밭 사이즈와, 배추를 입력 받을 때 주의해야할 것이 있는데 이 문제에서 가로의 길이M, 세로의 길이 N을 알려준다 2차원배열에서 첫번째 항목이 행, 두번째 항목이 열이기 때문에 (arr[row][col] 를 말함) M과 N을 입력받아 2차원 배열을 선언할 때 아래와 같이 선언하여야한다.

            arr = new int[N][M];

 

 

다른 문제에서는 0 1 0 0 이런식으로 0과 1로 배추가 있는 곳을 알려주는 경우가 있는데, 이 문제에서는 배추가 있는 곳의 '위치'를 알려준다. 그래서 이 위치가 곧 인덱스가 되어 2차원 배열에서 해당하는 위치를 1로 만들어주어 배추 땅을 완성한다. 

이렇게 배추를 입력받을 때도 X와 Y위치를 알려주는데 이것의 M,N의 범위이므로 위의 문단과 같은 이유로 arr[Y][X]와 같이 입력받아야한다.

                arr[y][x] = 1;

 

 

방문여부

이미 방문한 곳은 방문할 필요없이 전체적으로 1번씩만 방문여부를 체크하면 되기 때문에 방문 여부 변수는 static으로 선언해 main메서드와 bfs메서드 모두에서 사용할 수 있게한다.  

    static boolean[][] isVisit;

 

 

상하좌우 탐색

bfs/dfs를 많이 풀어본 사람이라면 상하좌우 탐색을 보자마자 아래와 같이 선언을 하였을 것이다

int[] dx = {-1,1,0,0}
int[] dy = {0,0,-1,1}

 

상하좌우 탐색을 위해서 dx와 dy배열을 왜 이렇게 선언을 하는지 모르겠다면 아래 설명을 참조하세요

 

 

 

3x3배열의 인덱스를 표현했습니다. 이 문제에서 행의 범위는 0부터 N-1, 열의 범위는 0부터 M-1입니다. 이 부분은 bfs메서드에서 범위에 벗어나는 부분은 탐색을 하지 않도록 continue를 걸어주어 패스하게 합니다. 

 

어쨌든 위의 그림에서 현 위치를 (1,1)이라고 하겠습니다. 그렇다면 위의 방향으로 이동을 한다고 가정을 해보겠습니다 '상'방향으로 이동하면 인덱스가 (0,1)로 변화하겠죠?

 

좌표로 표현하면 (1,1) -> (0,1) 와 같이 됩니다.

즉 x의 값이 1줄어들고, y의 값은 변화가 없습니다. 즉 인덱스의 '상'방향으로 이동 시 x,y 증감을 표현하면 (-1,0) 입니다. 

그렇다면 아래 방향으로 이동하면 x,y값은 어떻게 변할까요? (1,1) 에서 아래 방향으로 이동 시 (2,1)이 됩니다. 

(1,1) -> (2,1) 이므로 증감을 표현하면 (1,0)과 같이 됩니다. 

 

같은 원리로 상하좌우의 증감을 x,y좌표로 나타내면 아래와 같습니다. 

 

상 (-1,0)

하 (1,0)

좌 (0,-1)

우 (0,1)

 

그리하여 이것을 그대로 dx, dy배열로 표현하여 아래와 같은 값을 가지는 일차원 배열이 되는 것입니다. 

int[] dx = {-1,1,0,0}
int[] dy = {0,0,-1,1}

만일 대각선 방향으로도 탐색을 하는 경우라면 8방향이므로 dx, dy배열이 값을 8개씩 가지게 됩니다.

 

 

탐색진행

이 문제에서는 이미 방문한 곳은 다시 방문을 할 필요가 없이, 1번만 방문하면 끝인 케이스이다. (방문을 하고 다시 방문을 false로 한 뒤 재방문을 하거나 하는 문제가 아니다) 

 

- main()

int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!isVisit[i][j] && arr[i][j] == 1) {
                        bfs(i,j);
                        count++;
                    }
                }
            }

그렇기 때문에 main문에서 전체 배추 땅을 돌면서 배추가 있는 곳을 탐색한다. 이중 포문을 이용해 2차원 배열 전체를 탐색하게 하고, 방문하지 않은 곳이면서 배추가 있는 땅에서 bfs문을 실행한다.  

 

만일 방문하지 않은 땅이면서 배추가 심어있는 땅(1) 을 만났다면 그 인접한 땅은 모두 bfs문에서 방문 처리 된다. 그렇기 때문에 실제적으로 위의 이중 for문에서 if문을 만족하여 bfs을 실행하게 되는 것은 아래의 경우에만 해당한다.

 

Q. 1옆에 있는 1은 main()에서 방문하지 않나요?

상하좌우로 인접해 있기 때문에 bfs문에서 큐에 넣어 방문처리하게 된다. 즉 main에서 방문하지 않고, bfs문에서 방문하게 된다. 

 

처음에는 이해가 안갈 수 있지만 bfs가 어떻게 동작하는지 이해하고 나면, 당연한 것으로 받아들이게 된다. 그리하여main문에서는 저렇게 5곳에서 bfs문을 실행하게 되고, 동시에 count를 세게 하여 떨어져있는 배추 묶음이 몇 곳인지 세게 된다. 

 

 

- bfs()

static void bfs(int row, int col) {
        // 1번
        Queue<int[]> queue = new LinkedList<>();
        isVisit[row][col] = true;
        queue.add(new int[]{row, col});

        //2번
        while (!queue.isEmpty()){
            int[] temp = queue.poll();

            //3번
            for (int i = 0; i < 4; i++) {
                row = temp[0] + dx[i];
                col = temp[1] + dy[i];
                if(row<0 || col<0 || row>N-1 || col>M-1) continue;
                if(arr[row][col]==0 || isVisit[row][col]) continue;
                isVisit[row][col] = true;
                queue.add(new int[]{row, col});
            }
        }
    }

1번, 2번, 3번으로 나누어 설명하겠다.

 

위의 단락의 이유로 인해 main문에서는 '방문하지 않으면서 + 1인 곳' 에서 bfs문이 실행된다. 

 

1 bfs문 진입

매개변수로 들어온 열과 행에 해당하는 위치를 방문처리해준다. 

그리고 큐에 넣기 위해 큐를 선언하고 행, 열의 정보를 넣어준다. 

큐는 단일 값이 아닌 행, 열의 정보를 저장해야하므로 정수형 배열 타입  Queue<int[]> 으로 선언한다.

 

2 큐가 빌 때까지 while문 실행

큐에서 꺼낸 값을 임시 배열에 담는다. 

 

3 상하좌우 탐색

for문으로 상하좌우 4곳의 탐색을 진행한다. 아래 패스할 곳은 방문하지 않고 넘어간다.

 

패스할 곳

• 배열의 범위를 벗어나는 경우
• 이미 방문한 경우
• 배추가 없는 땅(0)

위의 경우에 해당하는 경우 continue를 통해 패스하도록 한다. 

 

방문하지 않으면서 배추가 있는 땅

상하좌우 탐색을 하면서 방문하지 않으며, 배추가 있는 땅은 방문 여부를 true로 하고, 큐에 넣는다.

아래는 bfs에서 세트로 생각하면 편하다. 

방문 = true;
큐.add(추가)

 

 

아래 첫 번째 bfs 탐색을 예로 들자

 

 

처음 탐색을 진행한다면 arr[0][0]이 방문하지 않으면서 1인 땅이므로 bfs문을 실행하게 된다 그러면 bfs문에서 위의 노란 체크와 같이 상하좌우 네곳을 탐색한다. 

 

상-범위 벗어남

하-0임

좌-범위 벗어남

우-OK

 

위와 같은 이유로 상,하,좌는 패스하게 되고 '우'의 경우만 큐에 넣고, 방문여부를 true로 체크하게 된다. 그 다음 큐에서 꺼내게 되는 것은 '우'에 해당하는 (0,1)의 위치이고 이 곳에 대해 다시 상하좌우 탐색을 진행하여 반복한다. 

 

상하좌우 탐색을 하고 해당하는 땅이 있으면 큐에 넣고 방문 여부를 true로 하고, 다시 큐에서 넣었던 곳에 대해 상하좌우 탐색을하고 해당 땅이 있으면 큐에 넣고 방문 체크하고,... 큐가 비면 탐색을 종료한다. 

bfs를 한 번 탐색을 할 때는 연결되어 있는 배추가 있는 위치들을 모두 방문하게 되고, 더 이상 주위에 배추가 없을 때는 탐색을 종료한다. 

 

bfs탐색은 처음에 코드를 보고 이해하려고 하기보다는 노트에 땅을 그려놓고 직접 상하좌우 탐색을 따라가보면서 큐의 변화와 방문 여부 변화를 보는 것을 권한다. 

 

 

◾정답코드

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 Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int M, N, K;
    static int[][] arr;
    static boolean[][] isVisit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            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];
            isVisit = new boolean[N][M];
            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;
            }
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!isVisit[i][j] && arr[i][j] == 1) {
                        bfs(i,j);
                        count++;
                    }
                }
            }
            sb.append(count+"\n");
        }
        System.out.println(sb);
    }
    static void bfs(int row, int col) {
        Queue<int[]> queue = new LinkedList<>();
        isVisit[row][col] = true;
        queue.add(new int[]{row, col});

        while (!queue.isEmpty()){
            int[] temp = queue.poll();

            for (int i = 0; i < 4; i++) {
                row = temp[0] + dx[i];
                col = temp[1] + dy[i];
                if(row<0 || col<0 || row>N-1 || col>M-1) continue;
                if(arr[row][col]==0 || isVisit[row][col]) continue;
                isVisit[row][col] = true;
                queue.add(new int[]{row, col});
            }
        }
    }
}

 

 

 

 

 

 

 

 

 

 

이해가 가지않거나 잘못된 내용이 있다면 댓글로 알려주시면 감사하겠습니다!