[백준 17142][C++] 연구소 3

문제

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

문제에서 주어진 제한 시간이 짧음에 주의하여 구현해야 한다.

 

풀이 과정

1. 주어진 입력에 주어진 바이러스의 위치 중 활성화할 바이러스를 선택할 수 있는 경우 탐색 알고리즘 구현(DFS, 조합 이용)

2. 선택된 바이러스의 위치에서 BFS를 통한 전이 함수 구현

3. 1에서 구현한 알고리즘을 통해 2를 반복하며 최소 전파시간 업데이트

4. 모든 탐색을 마친 후 최소 전파시간 출력

 

첫 제출에서 시간 초과 오답을 받았다. 이후 어느 부분에서 시간 초과가 발생하는지 찾기 시작했고, 생각보다 많은 시간이 소모되었다.

이때 개선한 내용은 두 가지가 있었다.

 

1)

DFS 알고리즘을 통해 탐색을 진행할 때, 탐색마다 BFS를 적용한 뒤 다음 단계로 넘겨주던 방식을 DFS로 조합할 좌표만 뽑아내서 M개에 도달하였을 때 해당 좌표들에 대해 BFS를 수행하도록 구현했다.

다시 자세히 설명하면, DFS탐색에서 불필요하게 BFS를 통해 수정한 map을 이전 map에 저장하고 되돌리는 과정에서 시간 소모가 많이 발생했을 것이라고 생각했다. 따라서 DFS탐색을 통해 퍼뜨릴 바이러스를 모두 선택한 뒤, BFS를 진행하도록 구현했다.

 

2)

DFS에서 중복되는 경우를 제외했다. 초기 DFS 구현에는 depth만 인자로 사용하여 탐색을 진행했기 때문에 탐색의 중복이 발생했다.

예를 들면 (1,2,3,4,5) 중 3개를 선택할 때 1,1,1 / 1,1,2 / 1,1,3 /... 이런 식으로 탐색을 진행했던 것이다. 

이를 depth와 idx 인자를 이용하여 1,2,3 / 1,2,4 / 1,2,5 /... 이런 식으로 중복 없이 탐색을 진행하도록 구현했다.

이게 얼마나 차이가 나겠어라고 생각했던 부분인데 수가 커질수록 정말 많이가 났다. (5*5*5*5*5 = 3125, 5*4*3*2*1 = 120)

 

 

세부 풀이

(1)

위에서 설명한 것 같이 DFS 알고리즘을 구현할 때 중복하는 경우를 최대한 제거하여 탐색 시간을 줄였다. chosen이라는 벡터를 이용하여 현재까지 선택된 값들을 저장하고, 원래 상태로 되돌리도록 구현했다. (이때 벡터라는 알고리즘이 pop_back 이 있기 때문에 구현이 용이했다.) 이때 DFS의 인자로 idx를 이용하여 탐색의 시작 index를 업데이트하며 중복을 피할 수 있다.

 

(2)

전형적인 BFS형태로 구현했으며, 이전에 방문했던 칸이더라도 현재 방문한 값과 비교하여 더 작은 값을 저장하도록 구현했다.

 

(3) (4)

DFS를 통해 뽑아낸 조합마다 BFS를 문제에서 입력받은 M번 진행한다. BFS를 진행한 뒤의 map의 상태를 통해 전파되지 않은 칸이 없다면 탐색하며 기록된 최대 시간을 최종 답안과 비교하여 더 작은 값을 최종 답안(ans)에 업데이트를 진행했다. 탐색이 끝난 뒤 ans값을 출력한다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>


using namespace std;


int N,M, ans=-1;
const int max_n = 50;
int map[max_n][max_n];
int original_map[max_n][max_n];
vector<pair<int,int>> virus_vector;
int num_virus;

void Input(){
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> original_map[i][j];
            if(original_map[i][j]==2) virus_vector.push_back({i,j});
        }
    }
    num_virus = virus_vector.size();
    memcpy(map,original_map, sizeof(int)*max_n*max_n);

}

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
void BFS(int ix, int iy){
    queue<pair<int,int>> q;
    int x = ix, y = iy;
    q.push({x,y});
    map[x][y]=0;
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int newX = x+dir[i][0];
            int newY = y+dir[i][1];
            //범위를 벗어나는 경우
            if(newX<0 || newX>=N || newY<0 || newY>=N) continue;
            //다음 좌표가 벽인 경우 제거
            if(original_map[newX][newY]==1) continue;
            
            //여기까지 왔다면, 벽이 아니고 빈칸이다.
            //0 인 경우는 한번도 방문 되지 않은 경우
            if(map[newX][newY] == 0){
                map[newX][newY] = map[x][y]+1;
                q.push({newX,newY});
            }
            //0 이 아닌 경우 중, 기존의 값보다 짧은 경로라면 업데이트한다.
            else if(map[newX][newY]>map[x][y]+1){
                map[newX][newY] = map[x][y]+1;
                q.push({newX,newY});
            }
        }
    }
}

vector<pair<int,int>> chosen;
vector<bool> visited;

void DFS(int depth, int idx){
    if(depth>M) return;
    if(depth==M){
        //DFS 탐색 마무리에서 BFS 시작으로 넘어갈 때
        //변화하는 map 값에 대해서 초기화를 진행한다.
        memset(map, 0, sizeof(int)*max_n*max_n);
        for(int i=0; i<M; i++){
            int x = chosen[i].first;
            int y = chosen[i].second;
            BFS(x,y);
        }


        //original_map 에서 0이었던 곳이 map에서도 0이 라면
        //해당 좌표가 바이러스에 전파되지 않은 지역이라는 뜻이다.
        int temp_max=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(original_map[i][j]==0){
                    if(map[i][j]==0)    return;
                    else{
                        temp_max = max(temp_max,map[i][j]);
                    }
                }
            }
        }

        //모든 경우 빈칸이 남아있다면,아래의 코드로 넘어오지 않았을 것이고,
        //그러면 ans 는 초기값 그대로 -1 일 것이다.
        if(ans==-1) ans = temp_max;
        else ans = min(ans, temp_max);

        return;
    }

    for(int i=idx; i<num_virus; i++){
        if(visited[i]) continue;
        visited[i]=true;

        int x=virus_vector[i].first;
        int y=virus_vector[i].second;
        chosen.push_back({x,y});

        DFS(depth+1, ++idx);
        visited[i]=false;
        chosen.pop_back();
    }
}

void solve(){
    for(int i=0;i<num_virus;i++) visited.push_back(false);
    DFS(0,0);
    cout << ans;
}



int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    Input();
    solve();
    return 0;
}

 

결과 및 후기

초기 제출 시 시간 초과가 발생하고 바로 잡는 과정이 정말 힘들고 오래 걸렸다. 하지만 그만큼 BFS / DFS 개념에 대해 깊게 따져보며 중복을 찾아볼 수 있는 기회였다.