백준 BOJ 2667번 - 단지번호붙이기

---

접근 방법

 

이번 문제도 DFS, BFS 문제다. 1012번 유기농 배추와 유사한 문제다. 아예 똑같다고 봐도 무방할 정도다.

https://edvedv.tistory.com/4?category=1038364 

백준 BOJ 1012번

 

그래프 유형의 문제는 유독 다 비슷비슷한 경우가 많으니 DFS, BFS를 확실하게 알고 넘어가야겠다.

---

코드

import java.util.*;
 
public class Main {
   static int[][] map;
   static boolean[][] visit;
   static int N;
   static int[] dx = { -1, 1, 0, 0 };
   static int[] dy = { 0, 0, -1, 1 };
   StringBuilder sb = new StringBuilder();
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      N = in.nextInt();
      map = new int[N][N];
      visit = new boolean[N][N];
      ArrayList<Integer> answer = new ArrayList<Integer>();

      for(int i = 0; i < N; i++) {
			String str = in.next();	
			for(int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
      for(int i = 0; i < N; i++){
         for(int j = 0; j < N; j++){
            if(map[i][j] == 1 && visit[i][j] == false){
               answer.add(bfs(i, j));
            }
         }
      }
      Collections.sort(answer);
      System.out.println(answer.size());
      for(int i : answer){
         System.out.println(i);
      }
      
      in.close();
   }
   public static int bfs(int x, int y){
      Queue<int[]> q = new LinkedList<>();
      q.offer(new int[] {x, y});
      visit[x][y] = true;
      int count = 1;
      while(!q.isEmpty()){
         int temp[] = q.poll();
         for(int i = 0; i < 4; i++){
            int next[] = new int[2];
            next[0] = temp[0] + dx[i];
            next[1] = temp[1] + dy[i];
            if(next[0] >= 0 && next[1] >= 0 && next[0] < N && next[1] < N &&
            map[next[0]][next[1]] == 1 && !visit[next[0]][next[1]]){
               q.offer(next);
               count++;
               visit[next[0]][next[1]] = true;
            }
         }
      }
      return count;
   }
}