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

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

2667번: 단지번호붙이기

 

---

💻 풀이 결과

💯 최종 코드

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
	int r, c;

	Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		char[][] map = new char[N][N];

		for (int i = 0; i < N; i++) {
			String str = sc.next();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		Queue<Node> queue = new LinkedList<>();
		LinkedList<Integer> list = new LinkedList<>(); // 각 단지 내 집의 수 저장할 리스트
		int[] dr = { 0, 0, -1, 1 };
		int[] dc = { -1, 1, 0, 0 };

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == '1') {
					queue.add(new Node(i, j));
					map[i][j] = '0'; // 방문처리
					int cnt = 1; // 각 단지 내 집의 수

					while (!queue.isEmpty()) {
						Node curr = queue.poll();

						for (int d = 0; d < 4; d++) {
							int nr = curr.r + dr[d];
							int nc = curr.c + dc[d];

							if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
								continue;
							}

							if (map[nr][nc] == '1') {
								queue.add(new Node(nr, nc));
								map[nr][nc] = '0'; // 방문처리
								cnt++;
							}
						}
					} // while문 끝

					list.add(cnt);
				}
			}
		}

		// 리스트 오름차순 정렬
		Collections.sort(list);

		System.out.println(list.size()); // 총 단지 수
		for (int i : list) {
			System.out.println(i);
		}
	}
}

💬 풀이 과정

• 리스트를 만들어 각 단지 내의 집의 수를 저장하였다.
• 방문처리 배열을 사용하는 대신에, 1을 0으로 처리해 줬다.

💡 깨달은 점

1. Collections.sort(리스트명)

• 리스트를 오름차순 정렬하고 싶을 때 사용

2. BFS 문제 반복

• 비슷하지만 조금씩 다른 BFS 활용 문제들이다. 반복 숙달할 필요가 있다.