백준[자바]_단지번호붙이기_2667_너비우선탐색

오늘은 백준 카테고리 중에서 그래프 순회에 있는 탐색 문제를 풀어보았다. 이번 문제는 BFS로 해결해보고자 한다. 

너비 우선 탐색은 자료구조로 큐를 이용하며 인접한 노드를 모두 방문한 후에 자식 노드로 넘어가는 특징이 있다. 

기본적인 너비 우선 탐색의 의사 코드는 다음과 같다. 

 

map -> 탐색 대상이 존재하는 전체 맵 
visit -> 중복 방문 방지용 방문배열(boolean) 
 
BFS(R){ -> R은 출발 노드 혹은 출발 지점
 
    Queue -> 방문할 노드를 저장할 큐를 생성. Enqueue하는 순간이 실제 방문이 아니라, 방문 해야할 노드의 리스트를 FIFO구조에 저장하는 것이다.
    visit[R] = true -> 시작 노드에 대해 방문 처리를 해준다. 기본적으로 방문 처리를 먼저 하고 큐에 enqueue한다. 
    Queue.add(R)    => 큐에 시작 노드를 인큐 한다. 
    
    
    while(!Queue.isEmpty()){ 큐에 더 이상 방문해야할 노드가 없을 때까지 아래의 과정을 반복한다.
        int a = q.poll()    -> 큐에서 가장 앞에 있는 노드를 꺼낸다. 이 시점이 실제로 노드를 방문하는 시점이라고 본다.
        
        조건  -> 문제에 따른 조건으로 한 번 필터링을 해준다. 
        
        if(!visit[a]){ 
            //아직 방문하지 않았다면 방문 처리를 해주고 인큐해주는 과정을 반복한다. 
            visit[a] = true;
            Queue.add(a);
        }
    }
}

 

그렇다면 이제 본격적으로 문제풀이를 위한 접근을 해보자

위의 의사코드를 기본 베이스로 두고 조건과 조건에 따른 자료구조만 추가해서 풀이할 것이기 때문에 여기에서는 풀이를 위한 조건만 체크해보도록 하겠다. 

• 아파트의 단지번호를 기억할 변수가 필요할 것 같다. 
  • 맵 전체를 입력받을 때, 같은 크기의 방문 배열을 선언해두고, 입력값이 0이라면(집이 없다면) 어차피 방문하지 않을 것이기 때문에 입력을 받음과 동시에 해당 위치에 true값을 줌으로써 방문 처리를 했다.
  • 초기화 작업이 끝나면 맵을 순회 하면서 처음으로 1을 만난 위치에서 너비 우선 탐색을 시작한다.
  • 탐색과정에서 상하 좌우를 이동할 수 있는 경우의 수를 모두 탐색한다. 이때 너비 우선 탐색을 시작하기 전에 전역 변수로 선언한 단지 번호를 +1 하고 시작한다. 
  • 탐색 과정에서 큐에 데이터가 enqueue될때마다 카운트를 해주면서 해당 단지에 속하는 집의 수를 카운트한다. 
  • 카운트한 집의 수를 따로 배열에 저장해두었다가 마지막에 정렬해서 출력한다. 
  • 가장 마지막으로 할당한 단지번호가 전체 단지의 수가 된다.

 

package BFS;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class _2667_단지번호 {
    //                       상 하  좌  우
    static int moveX[] = {-1, 1,  0,  0};
    static int moveY[] = { 0, 0, -1,  1};
    static boolean [][]visit;
    static int [][]danji;
    static int n;
    static int danjiNum=0;
    static int count=0;
    //같은 단지에 포함될 아파트의 개수를 저장할 배열 
    static int apart[];
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        
        danji = new int[n][n];
        
        visit = new boolean[n][n];
        apart = new int[n*n];
        
        //맵 초기화
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            for(int j=0; j<n; j++) {
                danji[i][j] = str.charAt(j)-'0';
                if(danji[i][j] == 0) {
                    visit[i][j] = true; //집이 없다면 미리 방문처리를 해둠으로써 이후에 방문 체크를 할때 연산식을 간편화 시킨다.
                }
            }
        }
        
        /*
         * for(int i[] : danji) { for(int a : i) { System.out.print(a + " "); }
         * System.out.println(); }
         */
        
        //탐색 시작 
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(!visit[i][j]) {
                    danjiNum++;
                    count=0;
                    bfs(i,j);
                }
            }
        }
        
        Arrays.sort(apart);
        sb.append(danjiNum).append('\n');
        
        for(int i : apart) {
            if(i==0) continue;
            sb.append(i).append('\n');
        }
        
        System.out.println(sb);
    }
    private static void bfs(int x, int y) {
        // TODO Auto-generated method stub
        Queue<pos> q = new LinkedList<pos>();
        
        
        visit[x][y] = true;
        q.add(new pos(x, y));
        apart[danjiNum]++;//단지번호가 같은 아파트의 수를 세어준다. 
        
        while(!q.isEmpty()) {
            pos cur = q.poll();
            int curX = cur.x;
            int curY = cur.y;
            
            for(int i=0; i<4; i++) {//현재 위치에서 상하좌우로 움직여본다.
                int nextX = curX + moveX[i];
                int nextY = curY + moveY[i];
                
                //아직 방문하지 않았고, 인덱스가 벗어나지 않는 경우
                if( nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && !visit[nextX][nextY]) {
                    visit[nextX][nextY] = true;
                    q.add(new pos(nextX, nextY));
                    apart[danjiNum]++;
                }
            }
            
        }
    }
 
}
class pos{
    int x;
    int y;
    
    
    public pos() {
        super();
    }
 
 
    public pos(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    
    
}
 
/*
    map -> 탐색 대상이 존재하는 전체 맵 
    visit -> 중복 방문 방지용 방문배열(boolean) 
    
    BFS(R){ -> R은 출발 노드 혹은 출발 지점
    
        Queue -> 방문할 노드를 저장할 큐를 생성. Enqueue하는 순간이 실제 방문이 아니라, 방문 해야할 노드의 리스트를 FIFO구조에 저장하는 것이다.
        visit[R] = true -> 시작 노드에 대해 방문 처리를 해준다. 기본적으로 방문 처리를 먼저 하고 큐에 enqueue한다. 
        Queue.add(R)    => 큐에 시작 노드를 인큐 한다. 
        
        
        while(!Queue.isEmpty()){ 큐에 더 이상 방문해야할 노드가 없을 때까지 아래의 과정을 반복한다.
            int a = q.poll()    -> 큐에서 가장 앞에 있는 노드를 꺼낸다. 이 시점이 실제로 노드를 방문하는 시점이라고 본다.
            
            조건  -> 문제에 따른 조건으로 한 번 필터링을 해준다. 
            
            if(!visit[a]){ 
                //아직 방문하지 않았다면 방문 처리를 해주고 인큐해주는 과정을 반복한다. 
                visit[a] = true;
                Queue.add(a);
            }
        }
    }
    
    
*/