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

접근 방법 🧐

예전에 풀었던 문제 인데 진짜 나는 dfs, bfs가 너무 어렵다..
우선 어떤 방법으로 풀어야할지도 감이 안 잡혀서 다른 분들의 글을 보다가 내 나름대로 기준을 정해봤다.
나만의 DFS BFS 판단 방법!

• 모든 아파트를 다 돌면서 "단지" 로 묶어줘야한다.
  →DFS
  
  
• 붙어있는 아파트들끼리 단지로 묶이니까, 방향 배열로 주변을 탐색해줘야한다
  →dx, dy배열
  
  
• 각 단지에 속하는 집의 수를 담아서 오름차순으로 정렬해서 출력해야한다
  → 단지가 몇 개 나올지 모르니까 ArrayList에 담아줄 것이다.
  
  

내가 쓴 코드 ✍️

import java.util.*;
import java.io.*;

public class Main {
	
	static int[][] danji;
	static boolean[][] visited;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	static List<Integer> result;
	static int cnt, N;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		result = new LinkedList<>(); 
		N = Integer.parseInt(br.readLine());
		danji = new int[N][N];
		visited = new boolean[N][N]; //단지에 속해있는지
		cnt = 1; //기준이 아파트(단지로 묶일 첫 아파트)가 포함될 때니 1로 초기화
		
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<N;j++) {
				danji[i][j] = str.charAt(j)-'0';
			}
		}
		
		
		for(int x=0;x<N;x++) {
			for(int y=0;y<N;y++) {
				if(danji[x][y]==1 && !visited[x][y]) {
					dfs(x,y);
					result.add(cnt);
					cnt = 1;
				}
			}
		}
		
		Collections.sort(result);
		
		bw.write(result.size()+"\n");
		for(int r : result) bw.write(r+"\n");
		bw.flush();
		bw.close();

	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0;i<4;i++) {
			int nx = dx[i]+x;
			int ny = dy[i]+y;
			
			if(nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny] && danji[nx][ny]==1) {
				cnt++;
				dfs(nx,ny);
			}
		}
	}
}

느낀점 📖

비슷한 문제인 유기농 배추 문제도 있다.

4개월전에 풀었던 문제였더라.. 그 당시에는 진짜 아무 생각 없이 구글에 검색해서 문제 풀고, 왜 dfs를 써야하는지도 몰랐다. 다시 풀어보니, 왜 dfs를 써야하는지도 감이 잡히고, 문제도 머리에 좀 더 잘 들어 왔다. 알고리즘 스터디하면서 이전에 풀었던 문제를 다시 풀어본 적이 몇 번 있는데, 이거 충분히 공부된다. 무엇보다 부계정으로 처음부터 실버 단계 문제들을 풀다보니, solved.ac 티어가 쑥쑥 올라가서 보는 재미도 있다ㅎㅎ


여유가 된다면 bfs로도 한 번 풀어보고 싶지만, 어떻게 하는지 모르겠다 헿 쪼렙..