[자바] 백준 2667 - 단지번호붙이기

풀때마다 새롭다. 신기하다.

네 방향을 왔다 갔다 할 수 있도록 2차원 int배열을 만들어서 for문으로 하나씩 que에 담아주는 부분이 항상 헷갈린다.

 int[][] dir = { {0,1}, {0,-1}, {1,0}, {-1,0} }; 

BFS에서는 que 안에서 if문의 조건을 제대로 세우는 단계가 제일 까다롭게 느껴진다.

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

public class Main2667_단지번호붙이기 {
	
	static int N;
	static int[][] map;
	static boolean[][] visited;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine().trim());
		map = new int[N][N];
		visited = new boolean[N][N];
		
		String[] str;
		
		for(int n=0;n<N;n++) {
			str = br.readLine().trim().split("");
			for(int m=0;m<N;m++) {
				map[n][m] = Integer.parseInt(str[m]);
			}
		}
		
		//bfs 메소드를 통해서 map[][]에 단지번호를 붙인다 
		//danjiNum = 1을 한 다음에, 실제로는 2부터 시작하도록 한다
		//단지가 있고 없고의 여부를 체크하는 1이랑 겹치면 안되니까! 
		int danjiNum = 1;
		for(int x=0;x<N;x++) {
			for(int y=0;y<N;y++) {
				if(map[x][y]==1 && !visited[x][y]) {
					danjiNum ++;
					bfs(x,y,danjiNum);
				}
			}
		}
		
		//map[]을 다시 돌면서 각 danjiNum마다 몇 개의 단지가 포함되어 있는지 카운트한다
		//이때 단지번호는 2번부터 시작하므로 
		int[] cntDanji = new int[danjiNum+2];
		for(int n=0;n<N;n++) {
			for(int m=0;m<N;m++) {
				if(map[n][m]>1) cntDanji[map[n][m]]++;
			}
		}
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i=2;i<=danjiNum;i++) {
			list.add(cntDanji[i]);
		}
		
		Collections.sort(list);
		sb.append(danjiNum-1+"\n");
		for (Integer i : list) {
			sb.append(i+"\n");
		}
		
		System.out.println(sb.toString().trim());
		
	}

	private static void bfs(int x, int y, int danjiNum) {
		visited[x][y] =  true;
		map[x][y] = danjiNum;
		
		Queue<int[]> que = new LinkedList<int[]>();
		que.add(new int[] {x,y});
		
		int[] tmp;
		int tmpX, tmpY;
		int newX, newY;
		while(!que.isEmpty()) {
			tmp = que.poll();
			tmpX = tmp[0];
			tmpY = tmp[1];
			
			int[][] dir = { {0,1}, {0,-1}, {1,0}, {-1,0} };
			for(int d=0;d<4;d++) {
				newX = tmpX + dir[d][0];
				newY = tmpY + dir[d][1];
				
				if(newX>=0 && newX<N && newY>=0 && newY<N 
						&& !visited[newX][newY] && map[newX][newY]==1) {
					visited[newX][newY] = true;
					map[newX][newY] = danjiNum;
					que.offer(new int[] {newX, newY});
				}
			}
		}
	}
}