/ BOJ

BOJ_2667_단지번호붙이기_JAVA

문제 : 단지번호붙이기

링크 : BOJ_2667_단지번호붙이기

접근 방식

DFS 또는 BFS를 이용하여 2차원 배열의 서로 인접한 노드의 개수를 탐색한다. 인접한 노드의 집합을 묶어서 카운트하고, 각 집합의 개수도 추가로 카운트한다. 최종적으로 2차원 배열의 인접한 노드의 집합의 개수와 각 집합의 노드 개수를 구하여 출력하면 된다.

풀이 방법

  1. 주어진 배열의 크기를 읽어들여 char타입 2차원 배열을 생성한다. 같은 크기로 boolean 배열도 함께 선언한다.(false 기본초기화)

  2. 생성한 2차원 배열에 입력값을 할당한다. 노드의 집합을 저장할 list를 하나 생성한다.

  3. 배열을 탐색하여 값이 ‘1’이면서 아직 방문하지 않은 노드일 경우 카운트를 1로 두고 DFS 메서드를 호출한다. 방문처리는 앞서 선언했던 boolean 배열을 이용한다.

  4. DFS를 이용하여 인접 노드를 순회한다. DFS는 재귀로 구현한다. 먼저, 해당 노드를 방문처리한다. 배열의 크기만큼 반복하는데, 해당 노드의 행에 아직 방문하지 않은 상태의 인접한 노드가 있다면, 해당 노드를 방문처리하고 재귀함수를 호출한다. 그리고 카운트를 1 증가시킨다.

  5. DFS 순회가 끝난 후 cnt값을 list에 추가하고 이어서 반복한다.

  6. 배열 탐색이 모두 끝나면 리스트를 정렬하여 리스트의 길이와 리스트에 들어있는 값을 출력한다.

소스 코드


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

public class BOJ_2667_단지번호붙이기 {
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	static boolean[][] isVisited;
	static int N;
	static char arr[][];
	static int cnt;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		List<Integer> list = new ArrayList<>();

		N = Integer.parseInt(in.readLine());

		// 값 저장할 배열
		arr = new char[N][N];
		// 방문상태 파악
		isVisited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			arr[i] = in.readLine().toCharArray();
		}

		// dfs
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == '1' && isVisited[i][j] == false) {
					cnt = 1;
					int cnt = dfs(i, j);
					list.add(cnt);
				}
			}
		}

		StringBuilder sb = new StringBuilder();

		Collections.sort(list);

		sb.append(list.size()).append('\n');

		for (int i = 0; i < list.size(); i++) {
			sb.append(list.get(i)).append('\n');
		}

		System.out.println(sb);

	}

	static int dfs(int x, int y) {

		isVisited[x][y] = true;

		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if (dx >= 0 && dx < N && dy >= 0 && dy < N && arr[dx][dy] == '1' && isVisited[dx][dy] != true) {
				dfs(dx, dy);
				cnt++;
			}
		}
		return cnt;
	}

}