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

1. 문제

 

 

2. 문제 풀이

지도의 크기 n을 입력받을 때, n의 최대가 25이므로 나중에 출력될 단지개수는 최대 313개가 나올 수 있다.
따라서 각 단지 내 집수를 저장할 배열 danji의 크기를 최대 큰 (n*n/2)+2개로 잡아주었다.
n+1사이즈의 map[n+1][n+1]을 for문을 돌면서 (1,1)부터 순서대로 이동시킨다. 
이때 값이 1이고 한번도 방문하지 않은 경우가 나오면 단지번호(cnt)를 하나 증가시키고 dfs함수를 호출한다.dfs함수에서는 넘어온 좌표는 이제 방문했음을 표시해야 하므로 visited배열에서 해당하는 좌표에 1을 넣는다.
그리고 해당하는 단지번호에 집 하나가 들어온것이므로 danji[cnt]를 하나 증가시켜준다.
이제 이 단지에 있는 집을 '오른쪽→아래→왼쪽→위쪽'의 시계방향 순으로 이동할 것이다.

여기서 이동하기 전에 먼저 고려해주어야 할 조건이 2가지가 있다.
1) map의 인덱스를 1부터 검색하였기 때문에 시계방향으로 검색할 때, 인덱스 0이 나오는 경우는 제외해준다.
   즉, (행의 인덱스)>1, (열의 인덱스)>1인 경우에만 이동해준다.
2) 행의 인덱스가 n인 경우 아래쪽으로 이동하면 배열의 길이를 초과하기 때문에 에러가 뜬다.
   마찬가지로 열의 인덱스가 n인 경우 오른쪽으로 이동하면 배열의 길이를 초과하기 때문에 에러가 뜬다.
   따라서 (행의 인덱스)<n, (열의 인덱스)<n인 경우에만 이동해준다.

따라서 시계방향으로 검색할 때
①위 두가지 조건을 만족하고
②값이 1이고
③한번도 방문하지 않은 경우
일때만 이동하고, 이동한 좌표를 기준으로 연결된 집을 검색하기 위해 dfs함수를 다시 호출한다.
최종적으로 연결된 집을 모두 찾았을때, 즉 마지막에 상하좌우에 이동할곳이 없을 경우에는 dfs함수를 처음 호출했던 좌표로 돌아와서 다시 for문을 돌면서 다음 단지를 찾는다.

출력값에는 총 단지 수, 그리고 각 단지내 집 수를 오름차순으로 출력해야한다는것에 유의한다.
처음에 이유를 모르고 계속 틀렸다고 나와서 시간을 꽤 오래 잡아먹었는데 오름차순이 잘못 짜여있어서 그런거였다..
결국 Arrays.sort()로 오름차순 해주니 오류없이 제출할 수 있었다. ★오름차순은 정리가 한번 더 필요할듯
 

3. 소스코드

package algorithm;

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

public class _2667 {
	static int n; // 지도크기
	static int[][] map; // 지도
	static int cnt = 0; // 단지 번호
	static int[] danji; // 단지
	static int[][] visited; // 방문했는지 체크

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		map = new int[n + 1][n + 1];
		visited = new int[n + 1][n + 1];
		int MAX_CNT = (n * n / 2) + 2;
		danji = new int[MAX_CNT];

		// 집 입력
		for (int i = 1; i <= n; i++) {
			String str = sc.next();
			for (int j = 1; j <= n; j++) {
				map[i][j] = str.charAt(j - 1) - '0';
			}
		}

		// 지도 (1,1)부터 방문
		for (int row = 1; row <= n; row++) {
			for (int col = 1; col <= n; col++) {
				if (map[row][col] == 1 && visited[row][col] == 0) { // 1이고 방문한적이 없으면
					cnt++;//단지 수 증가
					//시계방향으로 검사
					dfs(row, col, danji);
				}
			}
		}
		System.out.println(cnt); // 총 단지수 출력
		Arrays.sort(danji);

		for (int i = 1; i <danji.length; i++) {
			if(danji[i]!=0) {
				System.out.println(danji[i]);
			}
		}
	}

	// 시계방향 검색
	private static void dfs(int x, int y, int[] danji) {
		visited[x][y] = 1;
		danji[cnt]++;

		// 오른쪽
		if (y < n && map[x][y + 1] == 1 && visited[x][y + 1] == 0) {		
			dfs(x, y + 1, danji);
		}
		// 아래
		if (x < n && map[x + 1][y] == 1 && visited[x + 1][y] == 0) {
			dfs(x + 1, y, danji);
		}

		// 왼쪽
		if (y > 1 && map[x][y - 1] == 1 && visited[x][y - 1] == 0) {
			dfs(x, y - 1, danji);
		}
		// 위
		if (x > 1 && map[x - 1][y] == 1 && visited[x - 1][y] == 0) {
			dfs(x - 1, y, danji);
		}
	}
}