[BaekJoon] 백준 2667번 _ 단지 번호 붙이기 for JAVA _ DFS 알고리즘

 

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

2667번: 단지번호붙이기

 

 

문제

 

 

---

 

DFS로 풀었다.

 

 

딴건 몰라도 자바는 null때매 넘 짜증남... 특히 배열......

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;


public class Baek2667 {
	public static int[][] house = new int[25][25];
	public static int[] count_house = new int[625]; // 25 * 25
	public static int N, count = 0, i = 0;  // count = 총 단지 개수, i = 단지 아파트 개수
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < N; i++) { // house[][] 2차원 배열에 저장함
			String in = br.readLine();
			for(int j = 0; j < N; j++)
				house[i][j] = in.charAt(j) - '0';
		}

		
		for(int x = 0; x < N; x++) 
			for(int y = 0; y < N; y++) 
				if(block(x, y)) {
					count ++;
					i = 0;
				}
	
		System.out.println(count);
		

		Arrays.sort(count_house);  // 오름차순 해줘야함
		
		for(int i = 0; i < 625; i++)
			if(count_house[i] == 0) {}  // 오름차순 하면 비어있는 배열에 0이 들어있어서 0부터 나옴. 그래서 0 아닐때만 print
			else
				System.out.println(count_house[i]);

		
		
	}
	
	public static boolean block(int x, int y) {
		
		if(x <= -1 || x >= N || y <= -1 || y >= N) return false;
		
		if(house[x][y] == 1) {
			house[x][y] = 0;
			i++;
			block(x-1, y);
			block(x+1, y);
			block(x, y-1);
			block(x, y+1);
			count_house[count] = i;
			return true;
		}
		
		return false;
		
	}

}

 

이거 DFS 예시로 풀었던 음료수 얼려먹기 문제랑 비슷함 (https://ticssfm.tistory.com/66)

 

 

그래서 참고를 조금 했고....

 

 

나머지는 문제에 맞게.. 예를 들어 단지 내 아파트 개수가 가장 적은 것부터 출력이라던가...

 

이런거 신경써서 코딩해주면 된다.

 

 

저기 1차원 배열 가변으로 하고싶어서 선언 안했더니 null error 떴고

 

 

그 뒤로 엄청나게 헤매었다.. 극혐

 

 

그리고 아파트 개수 작은거부터 선언하면.. 그러니까 Arrays.sort() 하면

 

 

비어있는 배열 속 0부터 출력되기 때문에... print 할 때 0 아닌것만 출력하도록 조건으로 설정했다.

 

 

 

 

성능