BOJ2667 단지번호붙이기

<Solution>

1. 예전에 DFS로 푼 흔적이 있어서 BFS로 풀이

2. pair class 만들어서 단지내에 집이 있는 위치 x,y 저장하면서 인전한 곳 집이 있는지 계속 검사 q.add, q.poll 반복

---

<Source Code>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2667_단지번호붙이기 {
	
	static int[][] map;
	static int[][] visit;
	static int[] home;
	static int cnt;
	static int home_cnt;
	static int map_size;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), "");
		map_size = Integer.parseInt(st.nextToken());
		map = new int[map_size][map_size];
		home = new int[map_size * map_size];
		visit = new int[map_size][map_size];
		for(int i = 0; i < map_size; i++) {
			String str = br.readLine();
			for(int j = 0; j < map_size; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		for(int i = 0; i < map_size; i++) {
			for(int j = 0; j < map_size; j++) {
				if(map[i][j] == 0 || visit[i][j] == 1)
					continue;
				bfs(i, j);
			}
		}
		
		System.out.println(home_cnt);
		Arrays.sort(home);
		for(int i = 0; i < home.length; i++) {
			if(home[i] != 0)
				System.out.println(home[i]);
		}
	}
	
	static int[] dx = {0,1,0,-1};
	static int[] dy = {-1,0,1,0};
	
	public static void bfs(int x, int y) {
		visit[x][y] = 1;
		Queue<pair> q = new LinkedList<pair>();
		q.add(new pair(x,y));
		home_cnt++; // 단지 카운트
		cnt++; // 단지 내 집 수 카운트
		while(!q.isEmpty()) {
			pair p = q.poll();
			int px = p.x;
			int py = p.y;
			for(int di = 0; di < 4; di++) {
				int idx = px + dx[di];
				int idy = py + dy[di];
				if(idx < 0 || idx >= map_size || idy < 0 || idy >= map_size)
					continue;
				if(map[idx][idy] == 0 || visit[idx][idy] == 1)
					continue;
				cnt++;
				q.add(new pair(idx, idy));
				visit[idx][idy] = 1;
			}
		}
		home[home_cnt] = cnt;
		cnt = 0;
	}
	
	static class pair{
		int x;
		int y;
		public pair(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}