[백준(Baekjoon)][자바(java)] 2667 : 단지번호붙이기 / 그래프와 순회

 

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

2667번: 단지번호붙이기

 

문제 풀이

 

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

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), map[][] = new int[n][n], i, j, d;
		String s;
		for (i = 0; i < n; ++i) {
			s = br.readLine();
			for (j = 0; j < n; ++j)
				map[i][j] = s.charAt(j) - '0';
		}
		br.close();

		int cnt, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, pos[], x, y, nx, ny;
		boolean visited[][] = new boolean[n][n];
		Queue<int[]> queue; // x, y
		List<Integer> list = new ArrayList<>();
		for (i = 0; i < n; ++i) {
			for (j = 0; j < n; ++j) {
				if (map[i][j] == 1 && !visited[i][j]) {
					cnt = 1;
					visited[i][j] = true;
					queue = new LinkedList<>();
					queue.add(new int[]{i, j});
					while (!queue.isEmpty()) {
						pos = queue.remove();
						x = pos[0];
						y = pos[1];
						for (d = 0; d < 4; ++d) {
							nx = x + dx[d];
							ny = y + dy[d];
							if (nx < 0 || nx >= n || ny < 0 || ny >= n || 
								map[nx][ny] == 0 || visited[nx][ny])
								continue;
							cnt++;
							visited[nx][ny] = true;
							queue.add(new int[]{nx, ny});
						}
					}
					list.add(cnt);
				}
			}
		}

		Collections.sort(list);

		StringBuilder sb = new StringBuilder();
		sb.append(list.size() + "\n");
		for (int num : list)
			sb.append(num + "\n");
		System.out.println(sb.toString());
	}
}