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

문제

일단 생각하기!

• 데일리 실습 문제에 DFS 문제가 있어 DFS의 감을 완벽히 익힐 겸 추가로 풀이한 문제다. 구역의 수를 구하는 것은 [백준 10026번 적록색약]과 유사하지만 이 문제에서는 각각의 구역의 count를 따로 구해줘야 한다.
• 처음에는 구역의 수를 구하는 메소드와 각 구역의 count를 구하는 메소드를 따로 만들어 구현하려 했으나 같은 메소드에서 연산해도 된다! 구역의 수를 count 하는 것은 이중 for문 안에서 for문을 돌릴때마다 해주면 되고 구역 안의 집을 count 하는 것은 재귀를 호출할때마다 해주면 된다.
• 또한, 각 구역의 집 수를 셀 때 구역의 배열을 사용하려 했으나 인덱스를 연산하기 어려웠으며 리스트로 사용하는 것이 훨씬 편리하여 리스트로 바꿨다. (이 부분은 다른 사람의 풀이를 참고했다😅)

풀이

package BJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

/**
 * 
 * [문제] 백준 2667번 단지번호붙이기
 * [아이디어] DFS의 감을 익히려고 추가로 풀이한 문제
 * 적록색약 문제와 비슷한 점은 구역의 수를 구하는 것이고 다른 점이 있다면 각 구역의 count를 따로 구하는 것이다.
 * 처음엔 구역의 수를 구하는 메소드와 각 구역의 count를 구하는 메소드를 따로 빼려고 했으나 같이 연산을 해도 돼서 수정했으며
 * 또한 각 구역의 집 수를 구할때 배열을 사용하려 했으나 리스트로 사용하는 것이 훨씬 편리하여 수정하였다.
 * 
 * 메모리 : kb
 * 실행 시간 : ms
 * 
 * @author 김유나
 * 2023-08-21
 *
 */
public class BJ_2667_단지번호붙이기_김유나 {
	static int n, complex = 0, cnt;
	static int arr[][];
	static boolean isVisited[][];
	static int[][] deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine()); // 지도의 크기
		
		arr = new int[n][n]; // 지도 배열
		isVisited = new boolean[n][n]; // 방문 체크 배열
		ArrayList<Integer> houseCnt = new ArrayList<>(); // 각 구역의 집 수를 구할 리스트
		
		// int 타입 배열로 입력 받기
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < n; j++) {
				arr[i][j] = s.charAt(j) - '0';
			}
		}
		
		// 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 아직 방문하지 않았고, 1(집)일때
				if (!isVisited[i][j] && arr[i][j] == 1) {
					cnt = 0; // 각 구역의 집 수
					dfs(i, j); // 재귀함수 호출
					complex++; // 각 구역의 수
					houseCnt.add(cnt); // 리스트에 추가
				}
			}
		}
		
		Collections.sort(houseCnt); // 리스트 오름차순 정렬
		
		// 출력
		System.out.println(complex);
		for (int i = 0; i < complex; i++) System.out.println(houseCnt.get(i));
	}
	
	static void dfs(int x, int y) {
		isVisited[x][y] = true; // 방문 체크
		int current = arr[x][y]; // 가장 최근 값
		cnt++; // 각 구역의 집 수 ++
		
		// 사방 탐색
		for (int i = 0; i < 4; i++) {
			int dx = x + deltas[i][0];
			int dy = y + deltas[i][1];
			
			// 배열을 벗어날 경우 continue
			if (dx < 0 || dy < 0 || dx >= n || dy >= n) continue;

			// 아직 방문하지 않았고, 가장 최근 값과 같을 경우
			if (!isVisited[dx][dy] && arr[dx][dy] == current) {
				dfs(dx, dy); // 이동한 좌표로 재귀 호출
			}
		}
	}
}