[백준] 단지번호붙이기 2667번 - Java

[백준] 단지번호붙이기 2667번

나의 풀이

public class HouseNumbering {
    static int[][] graph = new int[25][25];
    static int N;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited = new boolean[25][25];
    static int count = 0;
    static int[] results = new int[25 * 25];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++) {
            String[] values = br.readLine().split("");
            for(int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(values[j]);
            }
        }

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(visited[i][j] == false && graph[i][j] == 1) {
                    dfs(i, j);
                    queue.add(results[count]);
                    count++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(count).append("\n");
        while(!queue.isEmpty()) {
            sb.append(queue.poll()).append("\n");
        }

        System.out.println(sb);
    }

    static void dfs(int x, int y) {
        visited[x][y] = true;
        results[count]++;

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];


            if(nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if(graph[nx][ny] == 1 && visited[nx][ny] == false) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

• BFS와 우선순위 큐를 사용하여 접근하였다.
• 배열이나 방향좌표 등 dfs에서 사용할 변수들을 클래스 변수로 선언한다.
• 입력 값들을 모두 받아준다.
• 입력이 완료되면 graph를 돌면서 graph의 해당 위치가 1이고 visited == false, 방문한 적이 없다면 해당 좌표를 가지고 dfs를 돌린다.
• 해당 좌표가 파라미터 값으로 dfs에 들어가면 해당 좌표를 방문처리 해주고, 해당 단지가 계속 이어져 있으면 results[count]를 통해서 해당 단지를 카운트해준다.
• 현재 입력받은 좌표로부터 상, 하, 좌, 우를 체크해준다. 만약 상, 하, 좌, 우가 graph의 볌위 안에 있고, 상, 하, 좌, 우의 좌표가 1이면서 방문한 적이 없다면, 재귀를 통해서 조건에 맞는 인접한 좌표들을 탐색한다.
• 인접한 위치에 더 이상 1이 없다면, 재귀는 종료될 것이고, 종료가 되면 오름차 순 정렬을 위해서 우선순위 큐에 results[count]를 추가해주고, conut를 1 증가시켜서 단지의 개수를 세준다.
• 반복이 끝나면 스트링 빌더를 사용해서 카운트를 추가해주고, 큐가 비어있지 않은동안 하나씩 꺼내어 스트링 빌더에 넣어주었다.
• 마지막으로 답이 담긴 스트링 빌더를 출력해 주었다.