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

그래프를 보는 순간, 전형적인 DFS, BFS문제 라는 것을 알 수 있다.

이 문제에서는 단지를 모두 찾아야 하므로 BFS, DFS모두 사용 가능하다.

나는 DFS가 사용하기 더 편했다.

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

public class Main {
	static String[][] map;
	static boolean[][] visited;
	static int n;
	static int houseCnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		map = new String[n][n];
		visited = new boolean[n][n];
		// 지도 입력
		for (int i = 0; i < n; i++) {
			String line = br.readLine();
			for (int j = 0; j < n; j++) {
				map[i][j] = line.substring(j, j + 1);
			}
		}

		// 지도 탐색
		List<Integer> villages = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 새로운 단지를 찾으면 dfs 시작
				if (map[i][j].equals("1") && !visited[i][j]) {
					houseCnt = 0;
					dfs(i, j);
					villages.add(houseCnt);

				}
			}
		}

		// 오름차순 정렬
		Collections.sort(villages);

		// 출력문 생성
		StringBuffer sb = new StringBuffer();
		sb.append(villages.size());
		for (int i : villages) {
			sb.append("\n" + i);
		}

		// 출력
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	static void dfs(int a, int b) {
		visited[a][b] = true;
		houseCnt++;
		if (a + 1 < n && !visited[a + 1][b] && map[a + 1][b].equals("1")) {
			dfs(a + 1, b);
		}
		if (a - 1 >= 0 && !visited[a - 1][b] && map[a - 1][b].equals("1")) {
			dfs(a - 1, b);
		}
		if (b + 1 < n && !visited[a][b + 1] && map[a][b + 1].equals("1")) {
			dfs(a, b + 1);
		}
		if (b - 1 >= 0 && !visited[a][b - 1] && map[a][b - 1].equals("1")) {
			dfs(a, b - 1);
		}

	}
}

dfs 메소드 내 if문에서 그래프의 범위를 잘 체크하자