[BOJ] 2667. 단지번호붙이기

문제

BOJ 2667. 단지번호붙이기

풀이

그래프 이론을 이용한 문제.
dfs와 bfs 중 bfs를 사용하여 풀었다.
집이 존재하는 경우에 arraylist에 넣고 list의 크기만큼 반복문으로 돌렸다.
해당 위치의 값이 아직 1이고 방문하지 않은 곳이라면 단지 번호가 붙여지지 않은 집이므로 해당 집의 위치를 인자값으로 넘겨주면서 bfs를 호출했다!
사방탐색하기 위해 만든 int형 배열을 이용하여 인접한 집들을 탐색하고 map의 범위를 벗어나지 않으면서 아직 방문되지 않은 집인 경우에만 로직 처리를 해주었다. queue에 아무것도 담겨있지 않다면 더이상 인접한 집이 존재하지 않다는 의미이므로 while문을 종료하고 해당 단지 내 집의 개수를 list에 담는다.

JAVA코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 백준2667_단지번호붙이기 {

	static int N;
	static int[][] map;
	static boolean[][] visited;
	static int[] di = { -1, 1, 0, 0 };
	static int[] dj = { 0, 0, -1, 1 };
	static ArrayList<Point> list = new ArrayList<Point>();
	static int count=0; //단지 수 카운트
	static ArrayList<Integer> numOfHouse = new ArrayList<Integer>();
	
	static class Point {
		int x;
		int y;

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

	}

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.valueOf(str.substring(j,j+1));
				if(map[i][j]==1) {
					list.add(new Point(i,j));
				}
			}
		}
		
		for(int i=0;i<list.size();i++) {
			Point point = list.get(i);
			
			if(map[point.x][point.y]==1&&!visited[point.x][point.y]) {
				bfs(point);
			}
		}
		
		Collections.sort(numOfHouse);
		
		System.out.println(count);
		for(int i=0;i<count;i++)
			System.out.println(numOfHouse.get(i));
	}
	public static void print() {
		for(int i=0;i<N;i++) {
			System.out.println(Arrays.toString(map[i]));
		}
		
		System.out.println("----------------");
	}
	public static void bfs(Point point) {
		Queue<Point> queue = new LinkedList<Point>();
		
		queue.offer(point);
		visited[point.x][point.y] = true;
		int num =1;
		count++;
		while(!queue.isEmpty()){
			
			Point current = queue.poll();
			
			for(int d=0;d<4;d++) {
				int ni = current.x + di[d];
				int nj = current.y + dj[d];
				
				if(ni<0||nj<0||ni>=N||nj>=N||map[ni][nj]==0||visited[ni][nj]) continue;
				
				map[ni][nj] = count;
				visited[ni][nj] = true;
				queue.offer(new Point(ni,nj));
				num++;
			}
			
		}
		numOfHouse.add(num);
	}

	
}