[BOJ] 2667 단지번호 붙이기 (DFS)

문제 출처: https://www.acmicpc.net/problem/2667

풀이법: 지도 배열의 모든 칸마다 방문하면서 1 값을 찾을때 마다 dfs를 진행한다.

 

Comment:

1) 입력: 배열 정보를 받을땐 string -> char형 배열 -> int형 배열로 변환하였다.

2) 단지 묶음 구분: 재귀함수 특성을 기억하면 제일 먼저 들어간 dfs함수가 끝난 시점 한 그룹에 대한 dfs가 끝난다는 사실을 알 수 있다.

3) dfs 함수 내 칸 이동 구현: 처음엔 if else if 문으로 오른쪽 이동 > 아래쪽 이동 > 왼쪽 이동 > 위쪽 이동 순으로 할려고 했으나 지도 밖

    으로 움직일 시에 대한 예외처리를 함께 하던 중 코드가 계속 꼬이는 문제가 발생하였다.

-> 이러한 문제는 칸 이동 전에 칸 이동에 대한 변수를 미리 구현하면 해결이 된다.

 

코드:

import java.util.*;

/*BOJ 2667*/

public class Main{
	static int count = 0	//단지 내에 집 수
    static int[][] map;		//지도
    static int[][] visited;	//방문 여부 확인 배열

	//칸 이동
	static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
	public static void main(String[] args){
    
    	int size;
    	PriorityQueue<Integer> pqueue = new PriorityQueue<>();	//단지 수 저장
    
    	Scanner sc = new Scanner(System.in);
    	size = sc.nextInt();
    
    	map = new int[size][size];
    	visited = new int[size][size];
    
    	//visited 초기화
    	for(int i = 0; i < size; i++){
    		for(int j = 0; j < size; j++){
       		 	visited[i][j] = 0;
     	   }
    	}
    
    	//map 입력
    	for(int i = 0; i < size; i++){
    		String input = sc.next();
       	 	char[] line = new char[size];
        	line = input.toCharArray();
        
        	for(int j = 0; j < size; j++){
        		map[i][j] = (int)line[j] - 48;
        	}
    	}
    
    	int i, j;
    
    	//dfs 진행
    	for(i = 0; i < size; i++){
    		for(j = 0; j < size; j++){
            	count = 0;
            	if(map[i][j] == 1 && visited[i][j] == 0){
                	dfs(i,j);
                    pqueue.add(count);
                }
            
            }
    	}
    	
        //결과 출력
        System.out.println(pqueue.size());
        
        while(!pqueue.isEmpty()){
        	System.out.println(pqueue.poll());
        }    
    }
    
    static void dfs(int i, int j){
    	visited[i][j] = 1;
        count++;
        
        //밑, 위, 오른쪽, 왼쪽 모든 방향에 대해 dfs
        for(int idx = 0; idx < 4; idx++){
        	int nextx = i + dx[idx];
            int nexty = i + dy[idx];
            
            if(nextx >= 0 && nextx < map[i].length && nexty >= 0 && nexty < map[i].length){
            	if(map[nextx][nexty] == 1 && visited[nextx][nexty] == 0){
                	dfs(nextx, nexty);
                }
            }
        }
    
    }
}