백준, BOJ, 14502번, 연구소 : C++ [CPP]

음..

생각은 빨리했는데.. 오래걸림..

왜냐면.. 초기화를 잘못했다.

 

아...내 1시간반

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

 

---

 

그렇게 어렵지 않았다.

벽을 무작위로 세워야 하는 것을 이미 알기에..

Brute Force를 해야하는 것은 알았지만 그냥 백트래킹 복습삼아 적용했다.

가장 처음 제출한 풀이..

#include <iostream>
#include <stack>
#include <vector>

#define X first
#define Y second

using namespace std;

int map[8][8];
int visited[8][8];

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

int N,M;
int ans = 64;


stack <pair<int,int>> stk; // DFS 스택
vector <pair<int,int>> vec; // 시작 위치




void func(int cnt){
    //벽 3개를 세움
    if(cnt == 3){
       //시작 스택
       for(auto x : vec){
           stk.push(x);
           visited[x.X][x.Y] = 2; // 2가 시작함
       }
       //DFS 실행
       while(!stk.empty()){
           auto cur = stk.top();
           stk.pop();
           for(int dir = 0; dir<4; dir++){
               int nx = dx[dir] + cur.X;
               int ny = dy[dir] + cur.Y;
               //범위에 벗어나면 해당 경로 이동불가
               if(nx< 0 || nx >= N || ny< 0 || ny>=M) continue; //범위에 벗어나면 해당 경로 이동불가
               if(map[nx][ny] == 1) visited[nx][ny] = 1; // map을 조사해서 해당 노드에 벽이 있으면 visited도 벽세움
               if(map[nx][ny] != 0) continue; // map에서 0인 노드만 바이러스 이동가능.
               stk.push({nx,ny}); // 해당 노드를 다시 넣고 DFS
               visited[nx][ny] = 2;// 해당 노드는 2가 된다.
           }
       }
       int safe = 0;
       //초기화
       for(int i=0; i<N; i++){
           for(int j=0; j<M; j++){
               if(visited[i][j] == 0) safe++;
               visited[i][j] = 0;
           }
       }
        
        if(safe<= ans) ans = safe;
        
        
    }
    else{
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                //선택
                if(map[i][j] == 0){
                    //벽세우기
                    map[i][j] = 1;
                    //다음 단계
                    func(cnt+1);
                }
                //복원
                map[i][j] = 0;
            }
        }
    }

}


int main(){
    
    
    cin >> N >> M;
    
    //행,row
    for(int i = 0; i<N; i++){
        //열,column
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
            //position of Virus
            if (map[i][j] == 2){
                vec.push_back({i,j});
            }
        }
    }
    
    func(0);
    
    
    
    
    cout << ans;
    
}

 

우선 visited을 제대로 체크하지 않은 것이.. 화근이었다.

 

다음은..

초기화를 백트래킹 하면서도..?

내가 백트래킹이 끝나면 visited을 초기화해서 문제가 생겼다.

기존에 있는 벽과 새로 생긴 벽은 그대로 냅두고 초기화했어야 했다.

#include <iostream>
#include <stack>
#include <vector>

#define X first
#define Y second

using namespace std;

int map[8][8];
int visited[8][8];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int N, M;
int ans = 0;


stack <pair<int, int>> stk; // DFS 스택
vector <pair<int, int>> vec; // 시작 위치




void func(int cnt) {
    //벽 3개를 세움
    if (cnt == 3) {
        //시작 스택
        for (auto x : vec) {
            stk.push(x);
            visited[x.X][x.Y] = 2; // 2가 시작함(방문처리)
        }
        //DFS 실행
        while (!stk.empty()) {
            auto cur = stk.top();
            stk.pop();
            for (int dir = 0; dir < 4; dir++){
                int nx = dx[dir] + cur.X;
                int ny = dy[dir] + cur.Y;
                //범위에 벗어나면 해당 경로 이동불가
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; //범위에 벗어나면 해당 경로 이동불가
                if (visited[nx][ny] != 0) continue; // visited에서 0인 노드만 바이러스 이동가능.
                visited[nx][ny] = 2;// 해당 노드는 2가 된다.
                stk.push({ nx,ny }); // 해당 노드를 다시 넣고 DFS
            }
        }

        //초기화
        int safe = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j] == 0) {
                    safe++;
                }
                else if (map[i][j] == 1 || visited[i][j] == 1) {
                    visited[i][j] = 1; //기존에 벽은 그대로 둠 (추가된 벽 + 원래 벽)
                }
                else {
                    visited[i][j] = 0; // 나머지는 초기화
                }
            }
        }
        if (safe >= ans) ans = safe;

    }
    else {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //선택
                if (map[i][j] == 0 ) {
                    //벽세우기(visited에다도 적용)
                    map[i][j] = 1;
                    visited[i][j] = 1;
                    //다음 단계
                    func(cnt + 1);
                    //복원
                    map[i][j] = 0;
                    visited[i][j] = 0;

                }


            }
        }
    }

}


int main() {


    cin >> N >> M;

    //행,row
    for (int i = 0; i < N; i++) {
        //열,column
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            //position of Virus
            if (map[i][j] == 2){
                vec.push_back({i,j});
            }
            else if (map[i][j] == 1) {
                visited[i][j] = 1;
            }
        }
    }

    func(0);

    cout << ans;

}

 

가장 무서운 것이

내가 하지 않았지만 했다고 생각하는 것이다.

왜냐면

모르거든... 난 이미 했는데 왜 안되는거지?하면서

이미 오류 요인에서 제외해버리기 때문이다.