백준[자바]_14502_BFS_DFS_연구소

오늘은 BFS문제를 풀이해보았다. 요즘 시간에 뒤쫓기며 계속 더 어려운 알고리즘, 아직 모르는 개념을 공부하는데만 몰두했었다. 오랜만에 탐색문제를 풀었는데, 생각보다 잘 풀리지 않았다. 그래서 위로만 올라가려고 하지 않고, 기본부터 단단히 잡으면서 가려고 한다. 

[ 문제 접근 ]

• 바이러스가 퍼지기 전에 3개의 벽을 세워서 바이러스가 퍼지지 않도록 반드시 막아야 한다. 
• 바이러스를 차단한 경우 남아있는 안전지대의 영역 수를 최대로 만들어야 한다. 
• 벽을 세우는 경우의 수는 어떻게 할 수 있을까? 
• 바이러스가 퍼지는 과정은 어떻게 포함할까?

문제를 풀기전에 혼자 생각을 해보았을 때, 벽을 세우는 경우의 수를 구하면 이 중에서 바이러스를 막을 수 없는, 즉 안전지대가 0인 경우의 수가 존재할 수도 있을 것이다. 그리하여 백트레킹 방식으로 바이러스를 막을 수없는 경우의 수는 바로 skip하도록 하려고 했지만,,,, 구현하지 못했다. 

이 문제에서 가장 핵심 적인 부분은 같은 배열을 사용하던 다른 배열을 따로 사용하던 자료구조에 대한 초기화가 이루어져야 한다는 점이다. 그래야만 여러 가지 경우의 수를 탐색할 때, 각각의 경우의 수에 대해서만 올바른 결과를 구할 수 있다.

[ 풀이과정 ]

1. 재귀로 구현한 순열을 구하는 알고리즘을 사용하여 벽을 세우는 경우의 수를 구하고 그 결과를 원본 맵이 아닌, 복사본에 벽 표시를 해준다. 재귀를 반복하다가, 재귀의 깊이가 3이 되면, 즉 3개의 벽을 모두 세웠다면, BFS를 시작한다.

코드의 위치를 알기 위해 class만 적어두었고, 중간에 생략된 내용이 있음을 미리 알린다.

전체 맵을 탐색하면서 벽이 없는 경우(값이 0)에만 첫 번째 벽을 세우고 나머지 2개의 벽은 재귀를 통해 세운다. 이 때 가장 중요한 부분은 모든 경우의 수를 탐색하기 위해서 재귀가 끝나고 돌아오면 이전에 세웠던 벽을 지워야 한다는 것이다.

public static void main(String[] args) throws Exception {
    
    //재귀를 진행하면서 벽을 세워보자.
    for(int i=0; i<n; i++) {
        for(int k=0; k<m; k++) {
            if(map[i][k]==0) {//아직 벽이 없다면,,,
                copy[i][k] = 1;
                dfs(1);
                copy[i][k] = 0; //재귀가 끝나서 돌아오면 다른 경우의 수를 위해서 벽을 부숴준다.
                
            }
        }
    }
    
    System.out.println(max);
    
}
 
private static void dfs(int wall) {
    // TODO Auto-generated method stub
    if(wall == 3) {
        //3개의 벽을 모두 만든경우 bfs탐색을 시작해보자
        bfs();
        return;
    }
    
    //나머지 2개의 벽을 더 세운다. 순열을 구하는 알고리즘을 응용한다.
    for(int i=0; i<n; i++) {
        for(int k=0; k<m; k++) {
            if(copy[i][k]==0) {//아직 벽이 없다면,,,
                copy[i][k] = 1;
                dfs(wall+1);
                copy[i][k] = 0; //재귀가 끝나서 돌아오면 다른 경우의 수를 위해서 벽을 부숴준다.
                
            }
        }
    }
    
}

 

2. 재귀 함수의 base-case에서 세개의 벽을 모두 세운 map을 사용하여 BFS 탐색을 시작한다. 

복사본은 벽을 세우는 경우의 수만 세기 위함이다. 이 맵에 바이러스가 전파되는 과정을 저장하면 배열을 매번 새로 초기화해야 하는 점을 방지하기 위해서 bfs전용 맵을 하나 더 생성해서 복사한 후에 bfs탐색을 진행한다. 

처음 입력받은 바이러스의 위치를 큐에 저장하고 시작한다.

private static void bfs() {
    // TODO Auto-generated method stub
    //방문배열을 초기화해줄 것 없이 bfs를 시작할때마다 새로 만들기
    visit = new boolean[n][m];
    Queue<Virus> q = new LinkedList<>();
    
    //이를 메인에서 정의하면 bfs를 돌때마다 새롭게 초기화를 해주어야 하므로 그냥 여기서 정의한다.
    virus_map = new int[n][m];
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            virus_map[i][j] = copy[i][j];
        }
    }
    
    //값을 입력받을 때, 저장한 바이러스의 위치를 큐에 저장한다. 이건 토마토랑 같은 방식으로 탐색하면 될 듯
    for(int i=0; i<virus.size(); i++) {
        Virus v = virus.get(i);
        visit[v.x][v.y] = true;
        q.add(new Virus(v.x, v.y));
    }
    
    while(!q.isEmpty()) {
        Virus now = q.poll();
        
        for(int i=0; i<4; i++) {
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            
            if(xx < 0 || yy < 0 || xx >= n || yy >= m ) continue;
            if(visit[xx][yy]) continue;
            
            if(virus_map[xx][yy] == 0) {//벽이 아니라면
                visit[xx][yy] = true;
                virus_map[xx][yy] = 2;
                q.add(new Virus(xx, yy));
            }
        }
    }
    
    countSafeArea();
}

 

3. 바이러스가 이동할 수 있는 인접 위치를 모두 탐색하면 안전지대의 개수를 계산해서 최댓값을 누적한다.

private static void countSafeArea() {
    // TODO Auto-generated method stub
    int cnt = 0;
    for(int i=0; i<n;i++) {
        for(int j=0; j<m; j++) {
            if(virus_map[i][j] == 0) {
                cnt++;
            }
        }
    }
    
    max = Math.max(max, cnt);
}