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

문제링크 : https://www.acmicpc.net/problem/2667

 

문제풀이

dfs, bfs로 풀 수 있는 문제이다.

 

1) 1인 지점을 찾아 그 지점부터 상, 하, 좌, 우로 깊이 우선 탐색을 한다.

2) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다.

 

3) 탐색이 끝나면 다시 1인 지점을 찾아서 깊이 우선 탐색을 한다.

4) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다.

 

5) 탐색이 끝나면 다시 1인 지점을 찾아서 깊이 우선 탐색을 한다.

6) 탐색을 하면서 countList에 집 갯수를 업데이트 하고, 탐색한 지점은 0으로 값을 바꾼다.

 

7) 더 이상 셀 집이 없다면 (1인 값이 없다면)

   countList의 사이즈(단지 수)와 값(각 단지에 속하는 집의 수)을 출력한다.

 

 

소스코드

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

public class p_2667 {
	static int N;
	static int[][] arr;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static LinkedList<Integer> countList = new LinkedList<Integer>();
	
	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];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		
		// 1인 것 찾기
		int index = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == 1) {
					// 0 추가
					countList.add(0);
					dfs(index++, i, j);
				}
			}
		}

		Collections.sort(countList);
		
		// 단지 수
		int count = countList.size();
		System.out.println(count);
		
		for (int i = 0; i < count; i++) {
			System.out.println(countList.get(i));
		}
	}
	
	public static void dfs(int index, int x, int y) {
		arr[x][y] = 0;
        // 집 개수 업데이트
		countList.set(index, countList.get(index) + 1);
		
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
				if (arr[nextX][nextY] == 1) {
					dfs(index, nextX, nextY);
				}
			}
		}
	}
}