백준 17142번 - 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

연구소 문제는 매우 유명한? 문제이기 때문에 한번 풀어보았다.

 

문제를 읽어보면 알겠지만 연구소 1과 비슷하게 백트래킹과 bfs를 사용하여 해결하면 될 것 같았다.

 

가장 걱정되었던 것은 시간제한이 0.25초인 거였지만 아무리 봐도 다른 풀이가 떠오르지 않아서 생각한 대로 구현해보았다.

 

풀이과정은 다음과 같았다.

 

1) 바이러스를 놓을 수 있는 모든 위치를 찾아놓음(최대 10개)
2) 모든 경우를 계산함
3) 이때 각 위치에서 bfs 돌림(초반에 queue에 한번에 다 넣으면
반드시 dis == 0인 지점을 동시에 방문함, 또한 dis == 1, 2,.. 인 지점들도 동시 방문
방문 체크만 잘해주면 한번의 bfs로 구할 수 있음)
4) 만약 max_dis구할때 이곳이 그 비활성 바이러스라면 건너뜀

 

내가 생각한 문제의 핵심은 "비활성 바이러스도 바이러스다! 즉 최대 시간에 넣지 않는다"였다.

 

뭐.. 이렇게 생각하고 구현하면 그다지 어렵지 않게 구현할 수 있었다.

 

뭔가 불안했지만 이게 맞겠지 하고 제출했는데...

 

음...

 

코드를 다시 보니 아무리봐도 bfs나 다른 구현들은 최적화를 다 했고, 더 시간을 줄일 수 있는 곳은 백트래킹뿐이라고 판단했다.

 

그래서 백트래킹 코드를 조금만 손봤더니..

 

 

근데 지금보니까 2~3분 사이에 100개가 넘는 제출이 있네요

 

역시 갓백준!

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int>pii;
 
int n, m, ans = 2555, cmp = 0;
int arr[55][55];
int dis[55][55];
bool check[55][55];
bool check_for_back_track[11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
vector<pii>vir;
vector<pii>temp;
 
pii bfs() {
    int ret = 0;
    int cnt = 0;
    memset(check, false, sizeof(check));
    memset(dis, 0, sizeof(dis));
    queue<pii>q;
    for (int i = 0; i < m; i++) {
        q.push(temp[i]);
        check[temp[i].first][temp[i].second] = true;
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (check[nx][ny] == false && arr[nx][ny] != 1) {
                    q.push(pii(nx, ny));
                    check[nx][ny] = true;
                    dis[nx][ny] = dis[x][y] + 1;
                    if (arr[nx][ny] != 2) { // 비활성 바이러스도 바이러스이기 때문에
                        ret = max(ret, dis[nx][ny]);
                        cnt++; // 즉 arr[nx][ny] == 0일때, 빈칸일때만 count됨!
                    }
                }
            }
        }
    }
    return pii(ret, cnt);
}
 
void back_track(int j) { // 간단한? 백트래킹 코드
    if (temp.size() == m) {
        pii p = bfs(); // p는 (최단 시간, 퍼진 바이러스의 개수)
        if (p.second == cmp) {
            ans = min(ans, p.first);
        }
        return;
    }
    for (int i = j; i < vir.size(); i++) {
        if (check_for_back_track[i] == false) {
            check_for_back_track[i] = true;
            temp.push_back(vir[i]);
            back_track(i + 1);
            check_for_back_track[i] = false;
            temp.pop_back();
        }
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2) vir.push_back(pii(i, j));
            else if (arr[i][j] == 0) cmp++; // 미리 빈칸의 개수를 가지고 있어서 계산하기 편함
        }
    }
    back_track(0);
    if (ans == 2555) ans = -1; // ans이 바뀌지 않았다면 모든 칸을 바이러스로 만드는 것 불가능
    cout << ans << "\n";
}