[백준 2667] 단지번호 붙이기

[문제 바로가기]👇

2667번: 단지번호붙이기

 

 

💡풀이💡

문제 정리!

1. 문제에서 지도에서 단지를 찾고 단지에 번호를 붙인다. 이 부분을 정리해 보면

단지 : 지도에서 연결된 집의 모임 → 연결되었다 = 집이 상하좌우로 붙어있다!
>> 그렇기 때문에 BFS or DFS 모두 가능!

 

2. 각 단지에 속하는 집의 수를 오름차순으로 정렬

단지 번호, 단지에 속하는 집의 수를 저장할 수 있는 클래스를 생성
>> 오름차순으로 정렬 해야 하기 때문에 Comparator를 사용하기 위해서 클래스로 정보 저장

 

 

1. 입력 받기

탐색 후 단지의 정보를 저장할 변수를 생성했는데,

각 지도마다 단지가 몇 개가 나올지 모르기 때문에 리스트로 생성을 했다.

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

// 단지 정보를 저장할 클래스
class Town {  
	int townNum;
	int houseCnt;
	
	public Town(int num, int cnt) {
		townNum = num;
		houseCnt = cnt;
	}
}

public class Main {
	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	static int[][] map; // 지도 저장
	static boolean[][] v; // 방문 했는지 확인
	static int townNum = 0; // 단지 번호
	static int houseCnt = 0; // 단지에 속한 집 수
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		List<Town> list = new ArrayList<>(); // 탐색 후 단지 정보를 저장할 리스트
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		v = 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] = str.charAt(j) - '0';
			}
		}
	}
}

 

2. 탐색하기 - BFS & DFS

지도를 모두 순회하면서 1) 방문하지 않았고 2) 집일 경우 탐색!

탐색이 끝나면 리스트에 단지 번호와 각 단지에 속한 집 수 추가하기

BFS와 DFS의 형식을 맞추기 위해 함수 시작하기 전에 변수를 조작

 

📌주의!

단지 번호

• 전체 지도 하나에서 새로운 단지가 시작할 때마다 계속 증가!
• 지도 하나에서 모든 단지가 하나의 townNum 변수를 공유

각 단지에 속한 집의 수

• 새로운 단지가 시작할 때마다 초기화 해야 함
• 단지가 시작할 때 집도 카운트를 해야 하기 때문에 1로 초기화

for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!v[i][j] && map[i][j] == 1) {
          townNum++; // 단지 
					houseCnt = 1;
					bfs(i, j);
					list.add(new Town(townNum, houseCnt));
				}
			}
		}

 

BFS

static void bfs(int i, int j) {
		Queue<int[]> q = new ArrayDeque<>();
		v[i][j] = true;
		q.offer(new int[]{i,j});
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			
			for(int d=0; d<4; d++) {
				int ni = pos[0] + dr[d];
				int nj = pos[1] + dc[d];
				
				if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj] && map[ni][nj] == 1) {
					v[ni][nj] = true;
					q.offer(new int[] {ni,nj});
					houseCnt++;
				}
			}
		}
	}

 

DFS

static void dfs(int i, int j) {
		v[i][j] = true;
		for(int d=0; d<4; d++) {
			int ni = i + dr[d];
			int nj = j + dc[d];
			
			if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj] && map[ni][nj] == 1) {
				dfs(ni, nj);
				houseCnt++;
			}
		}
	}

 

3. 단지 내 집의 수로 오름차순 정렬하기

Comparator 를 사용해서 Town타입의 리스트를 houseCnt 기준으로 정렬

• list는 Coolection이기 때문에 Collections.sort 사용

	Collections.sort(list, (o1, o2) -> Integer.compare(o1.houseCnt, o2.houseCnt));

 

 

4. 전체 코드

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

class Town {
	int townNum;
	int houseCnt;
	
	public Town(int num, int cnt) {
		townNum = num;
		houseCnt = cnt;
	}
}

public class Main {
	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	static int[][] map;
	static boolean[][] v;
	static int townNum = 0;
	static int houseCnt = 0;
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		List<Town> list = new ArrayList<>();
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		v = 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] = str.charAt(j) - '0';
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!v[i][j] && map[i][j] == 1) {
          townNum++;
					houseCnt = 1;
					bfs(i, j);
					//dfs(i,j);
					list.add(new Town(townNum, houseCnt));
				}
			}
		}
		
		sb.append(townNum).append("\\n");
		Collections.sort(list, (o1, o2) -> Integer.compare(o1.houseCnt, o2.houseCnt));
		
		for(Town t : list) sb.append(t.houseCnt).append("\\n");
		System.out.println(sb.toString());
	}
	
	static void bfs(int i, int j) {
		Queue<int[]> q = new ArrayDeque<>();
		v[i][j] = true;
		q.offer(new int[]{i,j});
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			
			for(int d=0; d<4; d++) {
				int ni = pos[0] + dr[d];
				int nj = pos[1] + dc[d];
				
				if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj] && map[ni][nj] == 1) {
					v[ni][nj] = true;
					q.offer(new int[] {ni,nj});
					houseCnt++;
				}
			}
		}
	}
	
	static void dfs(int i, int j) {
		v[i][j] = true;
		for(int d=0; d<4; d++) {
			int ni = i + dr[d];
			int nj = j + dc[d];
			
			if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj] && map[ni][nj] == 1) {
				dfs(ni, nj);
				houseCnt++;
			}
		}
	}
}