lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이 문제는 BFS만 잘 숙지하고 있으면 풀 수 있다.


아이디어 도출

  • 입력받은 단지 2차원 배열을 순회하면서 방문하지 않은 단지 위치라면 BFS 함수를 호출한다.
  • 총 단지의 수를 구할 변수와 단지별 집의 개수를 구할 변수를 구분하여 카운트한다.


위 아이디어를 토대로 입력받은 단지 배열의 1일 때마다 BFS를 호출하는데, BFS의 호출횟수가 총 단지의 개수가 된다. 그리고 BFS 함수 안에서 상하좌우로 노드를 탐색하는 횟수가 단지별 집의 개수가 된다.


그렇게 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

import java.io.*;
import java.util.*;

class Main {
    // BFS에서 x, y좌표마다 상하좌우러 이동할 배열 선언
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};
    // 방문 배열로 사용할 2차원 배열 선언
    static boolean[][] visited;
    // 입력받은 단지 2차원 배열 선언
    static int[][] arr;
    // 지도의 크기 N 전역변수
    static int N;
    // 총 단지수를 구할 변수
    static int danji;
    // 단지수별 집의 개수를 구할 변수
    static int danji_cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // N, 방문배열, 단지배열, 총 단지수 초기화
        N = Integer.parseInt(br.readLine());
        visited = new boolean[N][N];
        arr = new int[N][N];
        danji = 0;
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<str.length(); j++) {
                arr[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }
        
        // 각 단지별 집의 개수를 담을 List
        List<Integer> danjiCnts = new ArrayList<>();
        // 단지 2차원 배열을 순회하면서 방문하지 않은 단지 위치일 경우 다음을 수행
        // 1. 해당 위치가 1이라면 집이 존재하기에 해당 위치를 인자로 BFS 호출하고 danji 카운트 1 증가
        // 2. BFS 함수 내에서 단지별 집의 개수를 구하기 위해 danji_cnt를 1로 초기화
        // 3. BFS 호출이 끝나면 구해진 단지별 집의 개수 danji_cnt를 danjiCnts List에 삽입
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    danji_cnt = 1;
                    if(arr[i][j] != 0) {
                        danji++;
                        BFS(i, j);
                        danjiCnts.add(danji_cnt);
                    }
                }
            }
        }
        // 단지별 집의 개수를 오름차순으로 정렬
        Collections.sort(danjiCnts);

        bw.write(danji+"\n");
        for(int cnt : danjiCnts) {
            bw.write(cnt+"\n");
        }
        
        bw.close();
        br.close();
    }
    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;

        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int dir=0; dir<4; dir++) {
                int i = now[0] + dx[dir];
                int j = now[1] + dy[dir];
                if(0<=i && 0<=j && i<N && j<N) {
                    if(!visited[i][j] && arr[i][j] != 0) {
                        visited[i][j] = true;
                        // 단지별 집의 개수를 구해야 하기에 
                        // 상하좌우로 탐색하면서 같은 단지의 집의 개수를 danji_cnt에 1씩 카운트한다.
                        danji_cnt++;
                        arr[i][j] = arr[now[0]][now[1]]+1;
                        q.add(new int[]{i, j});
                    }
                }
            }
        }
    }
}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy