백준 14502 연구소 부르트포스로 풀기

목표: 백준 온라인 저지 14502 연구소 문제 풀기

환경: mac OS High Sierra 10.13.4, CLion

이 문제 완전탐색(부르트포스)으로 풀려고 합니다. 완전탐색이란 문제의 답을 찾는 것인데, 가능한 경우를 모두 나열하고, 각각이 해가 될 수 있는지 확인하는 방법입니다.

우선 완전탐색의 장단점을 얘기해보자면 장점으로는 어떻게든 답을 구해낼 수 있다는 것이에요. 모든 경우를 다 살펴보고 해를 구하는 것이니까요. 단점은 문제의 조건에 따라 오래 걸린다는 것인데, 이것을 최적화 하는 방법들이 있어요. 가지치기라든지 백트래킹이라든지

로직

시간복잡도를 계산하여 완전탐색을 했을시에 시간복잡도가 1억번 이하다? -> 완전탐색

그 이유는 전 실력이 부족하여 완벽하게 그리디 알고리즘으로 짤 수 없습니다.

그렇다면 시간제한안에 안전하게 답을 구하는 방법이 있다면?

모든 경우의수를 돌아도 그것은 좋은 방법중 하나입니다.

그래서 완전탐색으로 설계를 하였습니다.

우선 가능한 모든 경우의 수를 만들어 봅시다.

N(행),M(열)로 이루어진 2차원 배열에 빈칸에 벽을 3개 세울겁니다.

빈칸에만 벽을 세울수 있겠죠.

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if( map[i][j] == 0){
                //빈칸이면 벽을 세워보자
                map[i][j] = 1; // 1은 벽을 의미합니다.
                solve(cnt-1);
                map[i][j] = 0; // 0은 빈칸을 의미합니다. 되돌아왔을때는 기존 상태로 돌려놔야겠죠.
            }
        }
    }

위 코드가 익숙하지 않으신분들은 알파벳 문제를 빠르게 보시는게 좋습니다. 또는 최백준님의 N과M 문제집을 보시면 비슷한 유형문제가 많이 나옵니다. 재귀를 통해 조합문제를 푸는 것인데, NM가지중 3개 또는 N개를 뽑는 문제입니다. 뛰어나신분들이 해놓은 코드가 있으니 검색해보시길.

위와같은 solve함수를 얼마나 호출할건가? 세울 벽의 개수가 0일때까지 해야겠죠. 더이상 벽을 세울수 없으니까요.

벽을 세웠으니, 바이러스를 퍼트리고, 안전영역을 구해봐야겠죠. 바이러스는 인전한 빈칸으로 퍼집니다. 나를 방문하고, 나에 인접한 노드를 한번씩 방문한다. => 그래프 순회를 의미합니다. BFS, DFS중 BFS를 이용해서 구현하였습니다.

입력받을때 바이러스의 위치를 pair타입을 통해서 row,col 을 저장해놨습니다. 바이러스위치에서 BFS를 돌리는데 바이러스 개수만큼 돌리면 되겠습니다.

    if( cnt == 0){ //cnt는 세울 벽의 개수를 의미합니다.
        //안전영역 구하기

        //기본 맵 복사
        int tmp[MAX][MAX];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                tmp[i][j] = map[i][j];
            }
        }
        int size = (int)virus.size();
        for (int l = 0; l < size; ++l) {
            pair<int, int> tmp = virus[l];
            BFS(tmp.first, tmp.second);
        }
        int cnt = 0;
        for (int k = 0; k < N; ++k) {
            for (int i = 0; i < M; ++i) {
                if( map[k][i] == 0){
                    cnt++;
                }
            }
        }

        int res = cnt;
        if( ans < res){
            ans = res;
        }

        //안전영역 구한후 다시 기존맵 복원
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                map[i][j] = tmp[i][j];
            }
        }
        return;
    }

시간복잡도를 계산해보면 벽을 세우는 방법은 O(NM^3)입니다. 3번 세울건데, NM가지중 한개를 선택하는 방법의수 : NM 을 세번하여 NM * NM * NM 가 되고 BFS를 방문하는데 인접한 모든 노드를 방문할거니 O(NM)이 됩니다. NM 모든 노드를 한번씩 방문할거니까요.

[제약사항] 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

그렇다면 총 O(NM^4) = 약 1600만번입니다. 통상적으로 1억번을 연산하는데 1초걸린다하면 시간안에 수행가능한 프로그램입니다.

연구소

SourceCode