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

16 Apr 2026

Reading time ~3 minutes

내 풀이
다른 풀이

내 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N,cnt;
//	static int num;
	static List<Integer> ans = new ArrayList<>();
	static int[][] map;
	static boolean[][] check;
	static int[] dy = {1,0,-1,0};
	static int[] dx = {0,1,0,-1};
	public static void main(String[] args) {
		N = sc.nextInt();
		map = new int[N][N];
		check = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < N; j++) {
				map[i][j] = s.charAt(j)-'0';				
			}
		}
				
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {				
				if(map[i][j]==1 && !check[i][j]) {
//					num++;
					cnt = 0;
					dfs(i,j);
					ans.add(cnt);
				}				
			}
		}
		
		Collections.sort(ans);
		
		System.out.println(ans.size());
		for (int i = 0; i < ans.size(); i++) {
			System.out.println(ans.get(i));			
		}		
	}
	
	public static void dfs(int y,int x) {		
		check[y][x] = true;				
		cnt++;
//		map[y][x] = num;
		
		for (int i = 0; i < dy.length; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if(map[ny][nx]==1 && !check[ny][nx]) {							
				dfs(ny,nx);
			}
		}
	}
}

단지 번호가 같은 집의 개수를 cnt로 두고 dfs를 이용하여 그 개수를 센다. dfs가 끝나면 정답 리스트 ans에 그 개수를 추가한다. 단지 번호를 num이라고 둔 후 문제에 맞추어 단지 번호를 매기는 과정은 문제를 푸는 데 꼭 필요한 작업이 아니므로 주석으로 처리해 두었다.

다른 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N,cnt;
//	static int num;
	static List<Integer> ans = new ArrayList<>();
	static int[][] map;
	static boolean[][] check;
	static int[] dy = {1,0,-1,0};
	static int[] dx = {0,1,0,-1};
	public static void main(String[] args) {
		N = sc.nextInt();
		map = new int[N][N];
		check = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < N; j++) {
				map[i][j] = s.charAt(j)-'0';				
			}
		}
				
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {				
				if(map[i][j]==1 && !check[i][j]) {
//					num++;
					cnt = 0;
					dfs(i,j);
					ans.add(cnt);
				}				
			}
		}
		
		Collections.sort(ans);
		
		System.out.println(ans.size());
		for (int i = 0; i < ans.size(); i++) {
			System.out.println(ans.get(i));			
		}		
	}
	
	public static void dfs(int y,int x) {		
		check[y][x] = true;				
		cnt++;
//		map[y][x] = num;
		
		for (int i = 0; i < dy.length; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if(map[ny][nx]==1 && !check[ny][nx]) {							
				dfs(ny,nx);
			}
		}
	}
}

단지 번호를 의미하는 변수를 num으로 두고 dfs를 이용하여 group 배열에 단지 번호를 저장한다. 그 후 2중 for문을 이용하여 group 배열에 저장된 단지 번호가 같은 집의 개수를 세어 ans 배열에 저장한다. 이때 단지 번호 num은 1부터 시작하지만 ans 배열의 인덱스는 0부터 시작한다. 따라서 ans 배열의 num-1번째에 단지 번호가 같은 집의 개수를 센다.

DFS