[BOJ - JAVA] 1012 - 유기농 배추(BFS)

# 주소

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

1012번: 유기농 배추

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
import java.awt.Point;
public class Main{
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {1,0,-1,0};
    public static int n,width,height,m;
    public static int arr[][];
    public static boolean visit[][];
    public static ArrayList<Integer> list = new ArrayList<>();
    public static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        while(n--> 0){
            int count = 0;
            width = scan.nextInt();
            height = scan.nextInt();
            m = scan.nextInt();
            arr = new int[width][height];
            visit = new boolean[width][height];
            for(int i = 0; i < m; i++){
                int x = scan.nextInt();
                int y = scan.nextInt();
                arr[x][y] = 1;
            }
            for(int i = 0; i < width; i++){
                for(int j = 0; j < height; j++){
                    if(arr[i][j] == 1 && visit[i][j] == false){
                        bfs(i,j);
                        count++;
                    }
                }
            }
            list.add(count);
        }
        for(int i = 0; i < list.size(); i++){
            System.out.println(list.get(i));
        }
    }
    public static void bfs(int i, int j){
        int nx, ny;
        queue.offer(new Point(i,j));
        visit[i][j] = true;
        while(!queue.isEmpty()){
            Point now;
            now = queue.poll();
            for(int k = 0; k < 4; k++){
                nx = now.x + dx[k];
                ny = now.y + dy[k];
                if(nx >= 0 && ny >= 0 && nx < width && ny < height){
                    if(arr[nx][ny] == 1 && visit[nx][ny] == false){
                        queue.offer(new Point(nx,ny));
                        visit[nx][ny] = true;
                    }
                }
            }
        }
    }
}

이전에 푼 문제랑 상당히 흡사하죠?? 

이번에도 BFS 문제를 가져왔습니다. 

저는 공부방식이 DFS와 비슷하기 때문에.. 어느 한 문제에 꽂히면 그 문제 관련되서 많이 풀어가는 성격입니다. 

따라서 이 블로그를 제일 처음 포스팅했을 때는 주로 백트래킹에 관해서 풀어왔고, 이어서 DP, 그리디 등을 주로 하다가 요즘은 DFS, BFS 를 풀고 있습니다.

앞으로 당분간은 계속 DFS, BFS를 하지 않을까 싶네요! 푸는 것도 꽤 재미있고요 ㅎㅎ

다시 본론으로 들어가, 이 문제는 제일 처음 입력값으로 테스트 케이스 n개가 주어지고 해당 배열 arr의 width, height, 입력값의 개수 m이 주어집니다.

따라서 테스트 케이스에 따라 새로 문제를 풀어야할 경우에는(테스트 케이스가 2개가 주어지고 입력값이 2set로 주어질 때) while(n--> 0)을 이용하면 각 테스트 케이스에 따라 결과를 가져올 수 있으므로 상당히 유용하니 참고해주세요.

while안에서는 해당 배열 arr의 width, height, m을 입력 받고 그 다음 입력되는 해당 배열의 index값을 모두 1로 바꿉니다. 즉, 만약 1 1 2 2 4 5가 입력된다면 5x5배열의 경우

0	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	0	1
0	0	0	0	0

이런식으로 입력이 되는 경우가 됩니다. 그럼 여기서 bfs의 총 영역은 몇개일까요?

-->3개입니다.  왜냐하면 1이 입력된 값의 주변 인덱스들은 모두 0이기 때문에(대각선 제외) 영역은 3가지로 볼 수 있어 3개가 정답이 되어야 하는 것입니다.

그렇다는 것은, bfs에 인자 2개를 넣고 실행했을 때 해당 count를 계산할텐데, 그 count는 bfs의 영역의 개수를 의미합니다. 위의 이중 for문 안의 if문을 보시면 arr가 1이고 visit == false인 곳만 count를 증가시키는 것을 알 수 있는데, 그 말인 즉슨 위 표를 잘보시면 영역이면서 방문하지 않은 곳에 대해서만 count를 증가시켜야 진짜 bfs영역의 개수를 파악할 수 있습니다. 

그렇담 bfs의 내부 구조를 파악해봐야겠죠??

Queue<Point> queue 를 제가 선언했는데, 이전 문제에도 한 번 포스팅한 적 있습니다.

Queue를 Point타입으로 선언하게 되면, queue에 point가 입력됩니다. 그러니까, x나 y가 입력되는 것이 아니라 점의 타입으로 입력되는 것입니다. 이 때 사용할 떄 주의해야할 점이 있는데, queue.poll을 하게 되면 queue에 담겨 있던 모든 값이 날아가게 되므로 어느 인자를 선언하고(여기선 now) 그것에 담은 후 poll해야 안전하게 queue를 이용할 수 있습니다.

그리고 혹시나 nx,ny를 이해 못하시는 분이 계실까봐 정리해드리겠습니다.

nx와 ny는 현재 위치에서 dx , dy만큼 이동한 각각의 x와 y의 값입니다. 즉, dx가 -1이면서 dy가 0이라면 그건 왼쪽방향, dx가 1이면서 dy가 0이면 오른쪽 방향, dx가 0이면서 dy가 1이라면 위쪽, dx가 0이면서 dy가 -1이면 아래쪽 방향을 의미하는 것입니다. 

그러므로 bfs로 모든 인덱스를 탐색하기 위해서는 이중for문을 이용하고 그 내부에 if문(arr == 1이고 visit == false)을 반드시 작성해주고 if(nx와 ny가 0과 width, height 미만이라는 것을 꼭 작성해주어야 모든 arr를 탐색할 수 있는 것입니다. 그런데 이거 어디서 많이 봤죠??? 네 백트래킹이랑 상당히 비슷하죠?? 눈치 채셨다면 다행입니다 ㅎㅎ.

어쨌든 다시 본론으로 들어가, 만약 방문하지 않은 arr == 1인 곳에 한하여(이는 주변 index까지 모두 포함하여) queue에 인근의 점을 offer합니다.(offer는 queue에 점을 넣겠다는 의미) 그리고 해당 index의 visit을 true로 바꾸어주면 끝입니다!!!!!

다시 제일 위로 올라가 증가한 count들을 list에 담고 그 count를 차례로 출력해주면! 그것이 정답이 됩니다.

 

감사합니다!