[백준] 2667번: 단지번호붙이기(그래프, DFS)

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

2667번: 단지번호붙이기

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[][] map = new int[25][25];	// 집의 존재 입력할 2차원 배열
	static boolean[][] visit = new boolean[25][25];	// 탐색할 집의 방문 여부 체크
	private static int[] dx = {0, -1, 0, 1};	// dx, dy = 상하좌우
	private static int[] dy = {-1, 0, 1, 0};	
	static int count = 1;	// 방문한 단지 번호(연결된 단지가 아닐경우 1씩 증가)
	static int N;			// 지도의 크기
	
	// <- , ↑ , -> , ↓ ... 동서남북 4방향 체크해가며 dfs 돌리기
	public static void dfs(int x, int y) {
		map[x][y] = count;	// 방문한 집 => count로 표시(1, 2, 3, ... 하나씩 증가)
		visit[x][y] = true;	// 방문한 집 => true 체크
		for(int i=0; i<4; i++) {	// 상, 하, 좌, 우 체크
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			// nx, ny = 좌표의 범위, N*N 크기이므로 x, y좌표가 0보단 커야하고 N보단 작아야함.
			if(nx>=0 && ny>=0 && nx<N && ny<N) {	
				if(map[nx][ny] == 1 && visit[nx][ny] == false) {
					dfs(nx, ny);	// 1이면서 방문하지 않은곳 => dfs 돌리기
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();	// 지도의 크기
		for(int i=0; i<N; i++) {	// 2차원 행렬 입력받기
			String str = scan.next();
			for(int j=0; j<N; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j] == 1 && visit[i][j] == false) {
					dfs(i, j);	// 1이면서 방문하지 않은곳 => dfs 돌리고 단지수 카운트
					count ++;	// dfs 재귀 함수가 끝날때 => 탐색(인접)이 끝났으므로, 다음 인접된 집의 단지 번호를 +1 해줘야 함.
				}
			}
		}
		
		System.out.println(count-1);	// 단지수 출력
		int[] arr = new int[count];		// 단지수 만큼 집의 수 설정
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j] != 0) {	// 집이 있는 곳인 경우
					arr[map[i][j]] ++;	// 집이 있는 map[i][j]의 경우 count로 저장되었으므로, 단지 번호가 저장된다.
				}
			}
		}
		
		Arrays.sort(arr);
		for(int i=1; i<count; i++) 
			System.out.println(arr[i]);	// 각 단지번호 별로 단지수 출력
		scan.close();
	}

}

풀이

그래프 - DFS, BFS에서 응용된 문제이다.

다른 풀이들을 보니 dfs, bfs 두가지 방법 모두 풀수 있는데, 분류가 dfs로 돼있어서 dfs로 풀었다.

문제를 보면 1은 집이 있는곳, 0은 집이 없는 곳이다.

연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이는데 

연결되었다는 것은 어떠한 집의 상하좌우중 하나와 연결되어 있는 경우를 말한다. (대각선 X)

https://ldgeao99.tistory.com/400

즉 지도에서 집이 있는 곳(1)인 기점을 기준으로 dfs를 돌리는데 이 때 상하좌우를 기준으로 dfs를 돌린다.

dfs를 돌린 후 1인경우 재귀를 통해 계속 돌리고, 방문표시를 한다.

그 후 dfs의 호출이 끝났을 경우,, 다음 연결된 집을 찾기 위해 단지 번호를 증가시켜 준다.

기타 자세한 설명은 주석을 통해 설명했음 ....

 

아직 그래프나 재귀함수에 대한 이해가 완벽하진 않지만, 기존 dfs, bfs 원리에서 엄청 크게 응용이 되진 않았다. 

각 코드가 이해는 되지만 직접 구현하기는 좀 버거울 것 같다. 다양한 그래프 문제들 풀면서 이해하고 응용해봐야겠다 .

 

참고한 사이트

https://ldgeao99.tistory.com/400

챕터6-5. 그래프 | 문제풀이(2) - 플러드필 알고리즘(DFS, BFS 탐색응용)

 - dfs, bfs 응용 문제들 해설

 

 

https://pangsblog.tistory.com/28

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

 - 문제 풀이가 이해하기 쉽게 잘 되어있음.

 

 

https://justgo-developer.tistory.com/49

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

 - 참고한 코드