[BOJ]2667_단지번호붙이기(bfs)

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

낼모레가 정처기 시험이라 알고리즘 안풀려 했는데, 알고리즘 안푼다고 정처기 공부 더 하는 것 같지도 않다고 느꼈다. 외우는 공부는 이제 나이가 들어서 그런지 집중력 10분을 넘기지 못한다. 그러나 알고리즘 문제는 한시간은 거뜬히 집중할 수 있다는 것을 알기에 걍 이렇게 멍 때리고 유튜브보면서 공부 안할 바에 얼른 알고리즘 문제 하나 더 풀자고 생각했다. 

문제는 내가 좋아하는(?) bfs.(물론 bts노래는 더 좋아함). 푸는 방식이 정해져있기에 빨리 풀 수 있다.

 

문제의 키포인트는, bfs라고 처음부터 무작정 queue를 만들어서 때려넣자고 생각하는 것에서 벗어나는 것이다.

일단 전체 배열을 쭉 돌면서, 1을 발견하면 그때 큐에다가 넣는것이다. 이렇게 큐에 한번씩 넣을 때마다 단지의 수가 증가된다.

그리고 한 단지 내의 집의 수는 큐에다가 offer할때마다 카운트를 세주면 된다.

끝!

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

public class BOJ2667_단지번호붙이기 {
	static int N;
	static int[][] mat;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	static int cnt=0;
	static ArrayList<Integer> cntList = new ArrayList<Integer>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		mat = new int[N][N];
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<N; j++) {
				mat[i][j] = line.charAt(j)-48;
			}
		}

		bfs();
		System.out.println(cnt);
		Collections.sort(cntList);
		for(int i=0; i<cntList.size(); i++) {
			System.out.println(cntList.get(i));
		}
	}
	
	static class Point{
		int r;
		int c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	
	static int bfs() {
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				if(mat[r][c] == 1) {
					mat[r][c] = 0;
//					System.out.println("r,c: "+r+", "+c);
					cnt++;
					Queue<Point> qu = new LinkedList<>();
					qu.offer(new Point(r,c));
					int cntTemp=1;
					while(!qu.isEmpty()) {
						Point p = qu.poll();
						int nowR = p.r;
						int nowC = p.c;
						for(int i=0; i<4; i++) {
							int nr = nowR+dr[i];
							int nc = nowC+dc[i];
							if(nr>=0 && nr<N && nc>=0 && nc<N && mat[nr][nc]==1 ) {
								qu.offer(new Point(nr,nc));
								mat[nr][nc] = 0;
								cntTemp++;
							}
						}
					}
					cntList.add(cntTemp);
//					System.out.println(cntTemp);
				}
			}
		}
		return cnt;
	}
}