[Java/백준/DFS와 BFS] 2667 - 단지번호붙이기

문제

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

코드

DFS가 재귀를 써도 되기 때문에 자주 사용하게 된다.

입력받은 2차원 배열은 village에 저장한다.

dx, dy를 사용해서 상하좌우 좌표를 정해준다.

 

이중 for문을 돌면서 1인 좌표를 발견하면 dfs함수를 호출한다.

굳이 visited를 사용하지 않아도 dfs가 시작되면 village의 해당 좌표 값을 0으로 바꾸어 준다. (그럼 다음에 쓰루함)

해당 좌표에서 dx, dy로 상하좌우를 탐색하면서 만약 1이라면 dfs를 또 호출한다. 이런식으로 DFS가 진행된다.

함수가 끝나면 cnt의 값이 바뀌어 있음

 

마지막에 answer를 정렬 시켜주는 것을 잊으면 안된다.

 

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

class Main{
	final static int[] dx= {0,0,1,-1};
	final static int[] dy= {1,-1,0,0};
	static int num;
	static int cnt=0;
	static ArrayList<Integer> answer;
	
	public static void dfs(int[][] village, int i, int j) {
		cnt++;
		village[i][j]=0;
		for(int k=0; k<4; k++) {
			if(i+dy[k]<0 || i+dy[k]>=num || j+dx[k]<0 || j+dx[k]>=num)
				continue;
			else {
				int y=i+dy[k]; int x=j+dx[k];
				if(village[y][x]==1) {
					dfs(village, y, x);
				}
			}					
		}		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		num = Integer.parseInt(br.readLine());
		answer = new ArrayList<Integer>();
		int[][] village = new int[num][num];
		
		for(int i=0; i<num; i++) {
			String str = br.readLine();
			for(int j=0; j<num; j++) {
				village[i][j]=Integer.parseInt(str.substring(j,j+1));
			}
		}
		
		for(int i=0; i<num; i++) {
			for(int j=0; j<num; j++) {
				if(village[i][j]==1) {
					cnt = 0;
					dfs(village,i,j);
					answer.add(cnt);
				}
			}
		}
		
		bw.write(Integer.toString(answer.size()));
		bw.newLine();
		Collections.sort(answer);
		for(int cnt : answer) {
			bw.write(Integer.toString(cnt));
			bw.newLine();			
		}
		bw.flush();
	}
}