백준 2583 영역구하기 (dfs & bfs)

출처: https://www.acmicpc.net/problem/2583

---

소스코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Baek2583 {
    static int m, n, k;
    static int[][] canGo = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    static int [][] map;
    static List<Integer> sectionSizes = new ArrayList<Integer>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());//y
        n = Integer.parseInt(st.nextToken());//x
        k = Integer.parseInt(st.nextToken());
        map = new int[m][n];
        for (int i = 0; i < k; i++) { //색깔 칠하기
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            for (int y = y1; y < y2; y++) {
                for (int x = x1; x < x2; x++) {
                    map[y][x]=1;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(map[i][j]==0)
                    bfs(i, j);
            }
        }
        //영역의 크기를 오름차순 정렬하기 위함
        Collections.sort(sectionSizes);
        sb.append(sectionSizes.size()).append("\n");
        for (int i = 0; i < sectionSizes.size(); i++) {
            sb.append(sectionSizes.get(i)).append(" ");
        }
        System.out.println(sb.toString());
    }
    //bfs로 풀었지만 dfs를 이용하여 문제풀이 후 난중에 속도를 비교해 보는것도 좋을듯
    static void bfs(int y, int x) {
        Queue<int []> q = new LinkedList<>();
        int size = 1;
        q.offer(new int[]{y, x});
        //일종의 방문표시
        map[y][x]=1;
        while (!q.isEmpty()) {
            int[] prev = q.poll();
            for (int[] nextDir : canGo) {
                int ny = prev[0]+nextDir[0];
                int nx = prev[1]+nextDir[1];
                if(ny<0||ny>=m||nx<0||nx>=n) continue;
                if (map[ny][nx] == 0) {
                    q.offer(new int[]{ny, nx});
                    //일종의 방문표시
                    map[ny][nx]=1;
                    size++;
                }
            }
        }
        sectionSizes.add(size);
    }

}

느낀점 및 error 회고: bfs가 dfs에 비해 일반적으로 성능이 좋다. 깊이 우선 탐색(dfs) 너비 우선 탐색(bfs) 한글의미 그대로 되새기고 넘어가자. 처음에 bfs를 구현하는 부분에서 방문처리를 잘못하여 무한루프에 빠지는 경험을 했다. 맵을 탐색하다가 색칠된 영역이 아닌 첫번째 모눈종이부터 bfs를 수행하여 값을 찾아가야하는데 첫 모눈종이에서 방문처리를 하지않고 큐 내에서만 방문처리를 하여 무한루프에 빠졌던 것 같다.