[백준] 17141번 연구소 2 (C++)

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

 

 

이 문제는 격자가 주어지고 바이러스를 놓을 수 있는 위치가 주어질때 어느곳에 바이러스를 M개만큼 둬야 최소 시간동안

모든 격자에 바이러스가 다 퍼지는지 알아내는 문제이다.

 

바이러스를 놓을 수 있는 위치가 주어졌을때 그 위치에 놓는것이 최적인지 확인이 불가하기 때문에

모든 경우의 수를 구해야한다. 즉 바이러스를 놓을 수 있는 위치를 x라고 두고

놓을 수 있는 개수를 y라고 했을때

 

x \times y 로 표현할 수 있다.

 

 

1. 백트래킹으로 나올 수 있는 경우의 수를 구한다.

2. 이후 놓았던 바이러스를 시간이 지남에 따라 확장시킨다(bfs)

3. 이때 다 확장됬을 경우 최소 시간을 업데이트 한다.

 

이때 중요한 것은 바이러스를 퍼뜨리기 위한 새로운 배열을 하나 만들어야 하며 방문했는지 아닌지에 대한 배열을 따로 추가해야한다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M;
int graph[51][51];      // 0 : 빈칸, 1 : 벽, 2 : 바이러를 놓을 수 있는 칸
int C_Map[51][51];
vector<coordinate> virus;
bool visited[10];
bool check[51][51];
int result = MAX;
int tmpcnt;

void Copy() {			// 바이러스를 놓을 임시 배열 복사
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            C_Map[i][j] = graph[i][j];
            check[i][j] = false;
        }
    }
}

void Spread() {			// 바이러스 퍼트리기
    vector<coordinate> tmp;

    for(int i = 0; i < virus.size(); i++) {
        if(visited[i]) {
            tmp.push_back({virus[i]});
        }
    }

    int cnt = 0;

    for(auto it : tmp) {
        int x = it.x;
        int y = it.y;

        check[x][y] = true;
    }
    while(!tmp.empty()) {
        vector<coordinate> tmparr;
        for(auto it: tmp) {
            int x = it.x;
            int y = it.y;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

                if(C_Map[nx][ny] != 1 && !check[nx][ny]) {
                    tmparr.push_back({nx, ny});
                    check[nx][ny] = true;
                }
            }
        }
        tmp = tmparr;
        cnt++;
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(C_Map[i][j] != 1 && !check[i][j]) {
                return;
            }
        }
    }

    result = min(result, cnt);
}

void bt(int x, int cnt) {			// 바이러스를 놓을 수 있는 조합 구하기
    if(cnt == M) {
        Copy();
        Spread();
        return;
    }

    for(int i = x; i < virus.size(); i++) {
        if(!visited[i]) {
            visited[i] = true;
            bt(i+1, cnt+1);
            visited[i] = false;
        }
    }
}

void solve() {
    if(M == 0) {
        if(tmpcnt == 0) {
            cout << 0;
            return;
        }
    }

    bt(0, 0);

    if(result == MAX) {
        cout << -1;
    }
    else cout << result-1;
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> graph[i][j];

            if(graph[i][j] == 2) virus.push_back({i, j});		// 바이러스 위치 저장

            if(graph[i][j] != 1) {			// 벽이 아닌경우 카운트(격자가 모두 벽으로 이루어진경우 예외처리)
                tmpcnt++;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

구현하는데 30~40분 정도 걸린것 같다 중간중간 코드 실수가 있었고 답이 안나오는 경우, 모든 격자가 벽으로만 이루어지는걸

생각을 못했다 조금더 빨리 구현할 수 있게 계획을 잘 세워야할 것 같다.