[백준 2667] 단지번호붙이기 (JAVA)

백준 2667번 문제 - 단지번호붙이기 

2667번: 단지번호붙이기

---

문제 분석

 

 

• 정사각형 모양의 지도를 입력받는다.
• 입력에서 1인 경우는 집이 있는 곳, 0인 경우는 집이 없는 곳이다.
• 집이 연결되어 있는 경우 단지라고 한다.
• 지도에서 단지의 개수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 출력해라

---

해결 키 포인트

 

• BFS 문제
• 인덱스 x,y를 가지고 있는 Node 클래스를 생성해서 Queue에 넣는다.
• 큐에서 x,y를 뺀 후 해당 위치 상하좌우에 집이 있으면 다시 Node를 만들어서 큐에 추가한다.
  
  • 방문여부도 함께 확인
  • 큐에 넣을 때마다 sum 증가 및 방문 확인
• 결과 리스트에 sum 값 추가

 

---

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	public static boolean [][] isVisted;
	public static ArrayList<Integer> results = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int [][] nums = new int [N+2][N+2];
		for(int i=1;i<=N;i++) {
			String s = br.readLine();
			for (int j = 1; j <= N; j++) {
				nums[i][j] = (int)(s.charAt(j-1) - '0');
			}
		}
		
		isVisted = new boolean [N+2][N+2];
		
		for(int i=1;i<=N;i++) { 
			for (int j = 1; j <= N; j++) {
				if(nums[i][j] == 1 && !isVisted[i][j]) {
					int result = BFS(nums, i, j);
					results.add(result);
				}
			}
		}
		
		Collections.sort(results);
		
		System.out.println(results.size());
		for (int i = 0; i < results.size(); i++) {
			System.out.println(results.get(i));
		}
	}
	
	public static int BFS(int [][] nums, int x, int y) {
		Queue<Node> queue = new LinkedList<>();
		
		int [] dx = {1, 0, -1, 0};
		int [] dy = {0, 1, 0, -1};
		
		queue.add(new Node(x, y));
		isVisted[x][y] = true; 
		int sum = 1;
		
		while(!queue.isEmpty()) {
			Node value = queue.poll();
			
			int newX = value.x;
			int newY = value.y;
			
			for(int i=0;i<4;i++) {
				if(nums[newX+dx[i]][newY+dy[i]] == 1 
						&& !isVisted[newX+dx[i]][newY+dy[i]]) {
					sum++;
					queue.add(new Node(newX+dx[i], newY+dy[i]));
					isVisted[newX+dx[i]][newY+dy[i]] = true;
				}
			}
		}
		
		return sum;
	}
	
	static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x =x;
			this.y =y;
		}
	}
}