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

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

2667번: 단지번호붙이기

 

그리 어렵진 않은 탐색문제이다. 

 

DFS를 사용해 풀이해보겠다.

 

먼저 문제 분석을 하자면, 좌표에서 1에 해당하는 좌표에 인접한 1인 좌표가 있을 경우엔 같은 단지로 취급하고 

아닌경우는 다른 단지로 취급하고 0일땐 집으로 취급하지 않는다.

 

이때 단지의 수, 그리고 각 단지의 집의수를 오름차순으로 출력해주면 되는 문제이다.

 

 

우선 DFS로 구현을 하기위해 재귀 호출수를 저장할 변수,

그리고 NxN의 형태로 입력이 주어지므로 n을 저장할 변수를 선언해준다,

 

현재 1에 해당하는 좌표와 방문처리를 동시에 해줄 2차원 배열도 선언해주도록 한다.

 

그리고 상하좌우로 탐색하기 위해 dx, dy 배열도 선언해준다.

 

	static int n,call;
	
	static char[][] metrix;
	
	static int[] dx = { 1 , 0 , -1 , 0 };
	static int[] dy = { 0 , 1 , 0 , -1 };

 

다음은 dfs 메소드의 구현이다.

 

현재 좌표의 값이 0일때는 방문처리가 되었음으로 간주하고 바로 현재 메소드를 리턴해준다.

아닌경우엔 0으로 바꿔주어 방문처리후, 재귀호출의 수를 카운트 해준다.

 

그리고 dx,dy를 순회하면서 좌표범위를 벗어나지 않는 경우에만 재귀 호출을 해준다.

 

	static void dfs(int x, int y) {
		if(metrix[x][y] == '0') return;
		metrix[x][y] = '0';
		call++;
		for(int i = 0; i < 4; i++) {
			int nowX = x + dx[i];
			int nowY = y + dy[i];
			
			if(nowX >= 0 && nowY >= 0 && nowX < n && nowY < n) {
				dfs(nowX,nowY);
			}
		}
	}

 

 

이제 main에서는 반복문을 순회하며 1인 경우만 dfs를 수행하고 각 수행때마다 재귀호출횟수를 초기화 해주고

리스트에 값을 저장후 정렬후 출력해주면 된다.

 

주어진 예제에 대해 수행한 결과는 다음과 같다.

 

프로그램 실행결과

 

 

잘 실행되는것을 확인할수 있다.

 

아래는 코드의 전문이다.

 

package boj2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Boj2667 {
	
	/*
	 * DFS
	 */
	static int n,call;
	
	static char[][] metrix;
	
	static int[] dx = { 1 , 0 , -1 , 0 };
	static int[] dy = { 0 , 1 , 0 , -1 };
	
	static void dfs(int x, int y) {
		if(metrix[x][y] == '0') return;
		metrix[x][y] = '0';
		call++;
		for(int i = 0; i < 4; i++) {
			int nowX = x + dx[i];
			int nowY = y + dy[i];
			
			if(nowX >= 0 && nowY >= 0 && nowX < n && nowY < n) {
				dfs(nowX,nowY);
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(in.readLine());
		
		metrix = new char[n][n];
		
		for(int i = 0; i < n; i++) {
			String now = in.readLine();
			for(int j = 0; j < n; j++) {
				metrix[i][j] = now.charAt(j);
			}
		}
		
		in.close();
		
		List<Integer> list = new ArrayList<>();
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix[i][j] == '1') {
					call = 0;
					dfs(i,j);
					list.add(call);
				}
			}
		}
		
		Collections.sort(list);
		
		int size = list.size();
		
		sb.append(size).append('\n');
		
		for(int i = 0; i < size; i++) {
			sb.append(list.get(i)).append('\n');
		}
		
		System.out.print(sb);
		
	}

}