[실버1] 2667. 단지 번호 붙이기 (Java)

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

2667번: 단지번호붙이기

나는 주택살거야

---

※  문제를 요약하면 아래와 같습니다.

▶ N x N 크기의 지도에서 각 좌표에 집이 존재하면 1, 없으면 0

▶  각 집을 기준으로 상하좌우에 연속해서 집이 있을 경우 해당 집들의 모임을 단지로 정의

▶  단지의 갯수를 구하고, 각각의 단지 내 집 갯수를 찾기

▶  Input : 첫번째 줄에 집의 사이즈 N, 이후 N줄에 각각 N개만큼 0, 1 입력

▶  Output : 단지의 갯수, 각 단지 별 집의 갯수를 오름차순으로 출력

---

◈ Input - 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

◈ Output - 1

3
7
8
9

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 총 단지수 == DFS 횟수

▶ 집의 수 == DFS 시 탐색 횟수

▶ map으로 입력 받을 때 boolean 2차원 배열로 저장하여 1일 경우 true로 저장

▶ DFS를 재귀형태로 구현, 주어진 map 배열에서 각 좌표 별로 상,하,좌,우를 탐색하여 1일 경우 계속 탐색

▶ 상하좌우 탐색은 델타로 구현

▶ 탐색 시 방문처리 필수

▶ DFS 종료 (== 단지 1개 찾았다) 할 때마다 단지수 1씩 카운트

▶ 각 단지 별 집의 수를 ArrayList로 저장하여 오름차순 정렬

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static boolean[][] barrVisited;
	static boolean[][] barrMap;
	static int nCount;
	
	// 동서 남북
	static int[] dr = {0 , 0, 1, -1};
	static int[] dc = {1 , -1, 0, 0};
	public static void main(String[] args) throws IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(bReader.readLine());

		barrVisited = new boolean[N][N];
		barrMap = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			String strLine = bReader.readLine();
			for(int j = 0 ; j < N; j++) {
				if(strLine.charAt(j) == '1') {
					barrMap[i][j] = true;
				}
			}
		}
		
		ArrayList<Integer> listCounts = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!barrVisited[i][j] && barrMap[i][j]) {
					nCount = 0;
					DFS(i,j);
					listCounts.add(nCount);
				}
			}
		}
		
		// 오름차순 정렬
		Collections.sort(listCounts);
		// 출력
		bWriter.write(listCounts.size() + "\n");
		for(int i = 0; i < listCounts.size(); i++) {
			bWriter.write(listCounts.get(i) + "\n");
		}
		
		bWriter.flush();
		bWriter.close();
	}
	
	public static void DFS(int nRow, int nCol) {
		// 기저 조건
		if(barrVisited[nRow][nCol])
			return;
		
		// 탐색 조건
		nCount++; // 탐색 횟수 카운트 == 집의 갯수
		barrVisited[nRow][nCol] = true;
		for(int k = 0; k < dr.length; k++) {
			int nRowSearch = nRow+dr[k];
			int nColSearch = nCol+dc[k];
			
			// 동, 서, 남, 북 중 집이 있으면!
			if(nRowSearch >= 0 && nColSearch >= 0 
					&& nRowSearch < barrMap[0].length && nColSearch < barrMap[0].length 
					&& barrMap[nRowSearch][nColSearch])
				DFS(nRowSearch, nColSearch);
		}
	}
}

재밌군여~22

Good Luck! (피드백 감사합니다!)