BOJ 2667 단지번호붙이기

 

2667번: 단지번호붙이기

이 문제는 한칸의 위, 아래, 좌 , 우 에 1 표시가 되어있다면 (집이 있다면) 집이 연결되었다고 표현하고, 이렇게 연결된 집들을 '단지'라고 일컫는다. 

따라서 <그림 1>과 같이 생긴 그래프가 있을때 <그림 2> 와 같이 단지가 형성 되는 것이다. 각각의 단지는 서로 연결되어 있어서는 안된다. 

 

그렇다면 우리가 해야할 것은 모든 그래프를 돌아가며 단지 내에 집이 몇개가 있는지 계산하는 것이다.

 

이미 방문되었는지 여부를 나타내는 2차원 배열을 생성해야한다. 그후,

1) 그래프를 돌아가며 해당 그래프의 자리 graph[i][j]가 이미 방문되지 않았으며 graph[i][j]가 1인 노드를 찾는다.

2) 찾았다면 i, j 를 DFS 메서드에 넣어서 dfs를 진행해준다.

 

-> 여기서 DFS는 간선으로 연결되어있는 노드를 DFS하는 것이 아니라, 문제의 조건대로 "위, 아래 양 옆"에 있는 노드를 재귀적으로 DFS해준다.

-> 이렇게하면 당연히 "재귀의 깊이 == 해당 단지 내의 집" 이 된다. 왜냐하면 모든 재귀가 끝나고 돌아왔다는 것은 더이상 탐색할 노드 (집) 이 없다는 것이기 때문이다.

따라서 DFS 아래와 같이 구현된다.

private static void dfs(int i,int j) {
	count++; //재귀의 깊이 
	visited[i][j]=true; //visited 표시 
	if(i!=0&& visited[i-1][j]!=true && graph[i-1][j]==1) 
		dfs(i-1,j); //윗 노드 (outofRange에러를 방지하기 위해 i가 0이 아님이 조건이어야 한다.)
	if(i!=n-1&&visited[i+1][j]!=true && graph[i+1][j]==1)
		dfs(i+1,j); //아래 노드 (outofRange에러를 방지하기 위해 i가 n-1이 아님이 조건이어야 한다)
	if(j!=0&&visited[i][j-1]!=true && graph[i][j-1]==1)
		dfs(i,j-1); //왼쪽 노드 
	if(j!=n-1&&visited[i][j+1]!=true && graph[i][j+1]==1)
		dfs(i,j+1); //오른쪽 노드 
}

-여기서 꼭 경계값에대한 조건문을 맨 처음에 넣어주어야 한다. 

-count는 재귀의 깊이를 센다 . 곧 이는 dfs로 탐색 할 수 있는 노드의 개수이므로 해당 단지 내의 집 수를 나타낸다. 따라서 dfs가 끝나면 count를 정해진 배열에 저장한 후, count를 0으로 초기화해준다.

 

 

그렇다면 전체 소스를 보도록하자.

자바 전체소스 

import java.util.*;
import java.io.IOException;
import java.util.Arrays;
public class Main {
	private static int count=0;
	private static int [][]graph= new int[25][25];
	private static boolean[][]visited; // 방문체크 
	private static int index=0;
	private static int n;
	private static void dfs(int i,int j) {
		count++;
		visited[i][j]=true;
		if(i!=0&& visited[i-1][j]!=true && graph[i-1][j]==1) {
			dfs(i-1,j);
		}
		if(i!=n-1&&visited[i+1][j]!=true && graph[i+1][j]==1)
			dfs(i+1,j);
		
		if(j!=0&&visited[i][j-1]!=true && graph[i][j-1]==1)
			dfs(i,j-1);
		if(j!=n-1&&visited[i][j+1]!=true && graph[i][j+1]==1)
			dfs(i,j+1);
		}
		
	public static void main(String[] args) throws IOException 
	{
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		graph= new int[n][n];
		visited = new boolean[n][n];
		int[] ans = new int[n*n]; //각 단지에 존재하는 집의 수. 
                                  
		
		for(int i=0; i<n; i++){ //i, j 입력 
            String input = in.next(); //string으로 입력 받은 후 
            for(int j=0; j<n; j++){
                graph[i][j] = input.charAt(j)-'0'; //char 에서 '0'을 빼준다.
            }
        }
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(graph[i][j]==1 && visited[i][j]==false) {
					dfs(i,j);
					ans[index]=count; //ans 배열에 저장 
					index++; // index는 총 단지의 수를 나타낸다.
					count=0; //count 초기화 
				}
			}
		}
		
		Arrays.sort(ans); //ans 배열 소팅 
		System.out.println(index); 
		for(int element : ans ) {  
			if(element!=0) { 
			System.out.println(element);}
			
		}
		
		
	}
}