[백준] 2667 단지번호붙이기 - Graph Theory / Java

• 문제 링크

2667번: 단지번호붙이기

 

• 풀이 과정

0 과 1을 입력받아 단지의 형태를 나타내는 2차원 배열을 생성하고

전체 노드를 탐색하여 0 이 아닌, 즉 방문 가능한 노드를 시작 노드로 하나의 연결 요소로써 탐색한다.

 

배열의 범위 내의 연결된 노드의 값이 1인 위치을 찾아가며,

방문한 위치마다 0 으로 변경하고 cnt 변수에 1을 더하여 해당 연결요소의 방문한 모든 노드의 개수를 반환한다.

 

반환한 값은 List 자료구조에 저장되며 최종적으로 연결 요소의 개수를 의미하는 list.size() 와,

해당 List 의 요소를 정렬하여 순차적으로 정답으로써 출력한다.

 

• 풀이 코드

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.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

	static int n;
	static int[][] map;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < n; j++)
				map[i][j] = input.charAt(j) - '0';
		}
		
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] != 0) 
					list.add(bfs(i, j));
			}
		}	
		bw.write(list.size() + "\n");
		
		Collections.sort(list);
		for (int i : list) 
			bw.write(i + "\n");
		
		bw.flush();
	}

	private static int bfs(int y, int x) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(y, x));
		map[y][x] = 0;
		
		int cnt = 1;
		while (!q.isEmpty()) {
			Node now = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];

				if (ny < 0 || nx < 0 || ny >= n || nx >= n)
					continue;
				if (map[ny][nx] == 0)
					continue;

				q.offer(new Node(ny, nx));
				map[ny][nx] = 0;
				cnt++;
			}
		}

		return cnt;
	}

	private static class Node {
		int y;
		int x;

		Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

}