BOJ_2667 : 단지번호붙이기

👉 문제링크

2667번: 단지번호붙이기

---

---

🔸 문제 분석 🔸

• n X n 지도에서 붙어있는 집 (1)을 찾아 단지 별로 구분한다.
  • 단지의 수와 각 단지별 집의 수를 오름차순으로 출력한다.
• BFS로 탐색해 붙어있는 집의 수와 단지 수를 구한다.

🔸 코드 🔸

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 1) input
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < n; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }

        // 2) BFS
        int dangi = 1;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        boolean[][] visit = new boolean[n][n];
        Stack<Pair> stack;
        ArrayList<Integer> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                stack = new Stack<>();
                stack.push(new Pair(i, j));
                int count = 0;

                while (!stack.isEmpty()) {

                    Pair pair = stack.pop();

                    if (0 <= pair.x && pair.x < n && 0 <= pair.y && pair.y < n && !visit[pair.x][pair.y] && arr[pair.x][pair.y] == 1) {

                        count++;
                        visit[pair.x][pair.y] = true;
                        arr[pair.x][pair.y] = dangi;

                        for (int k = 0; k < 4; k++) {
                            stack.push(new Pair(pair.x + dx[k], pair.y + dy[k]));
                        }
                    }
                }
                if (count > 0) {
                    answer.add(count);
                    dangi++;
                }
            }
        }

        Collections.sort(answer);
		
        // 3) print
        System.out.println(dangi - 1);
        for (int i = 0; i < dangi - 1; i++) {
            System.out.println(answer.get(i));
        }
    }

    private static class Pair {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

🔸 코드 해석 🔸

• 1) 지도의 한 변의 길이 n과 nxn 지도 정보를 입력받아 int형 2차원 배열 arr에 저장한다.
• 2) BFS로 단지를 탐색한다.
  • 모든 집을 시작 노드로 넣어본다.
  • 스택이 빌 때까지 계산을 반복해 같은 단지 소속의 집들을 찾는다.
    • x, y가 지도 내의 범위이며, 방문하지 않은 집이고, 값이 1이면 방문하고 주변 집을 탐색한다.
  • count > 0 : 한 집이라도 방문했으면 단지이므로, 단지 수를 늘리고 집의 수를 answer에 저장한다.
  • answer를 오름차순 정렬한다.
• 3) 단지 수 dangi 와 answer 의 요소를 출력한다.

---

🔸 end 🔸

• BFS로 풀 수 있는 간단한 문제였다.
• 테스트케이스도 여럿 만들고 공유도 해보았다.

// 1) : 1 25

5
11111
11111
11111
11111
11111

// 2) : 3 4 20 36

10
1111111111
1000000001
1011111101
1010000101
1010110101
1010110101
1010000101
1011111101
1000000001
1111111111

// 3) : 1 96

25
1111111111111111111111111
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1000000000000000000000001
1111111111111111111111111


// 4) : 50 1 1 1...(46)...1

10
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101

• 문제 분석, 코딩 계획을 미리 써보며 풀이했다.