백준 17142 연구소 3

작성일 | In |

Problem : 연구소 3

유형 : 구현, BFS

문제 해석

  • 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하라

문제 재해석 (7)

  • 바이러스 목록 중 활성화 할 바이러스 몇개를 뽑는다.
  • 활성화된 바이러스는 1초마다 4방향으로 퍼져나간다
  • 벽인 경우 바이러스가 퍼져나가지 못한다.
  • 활성화 되지 않은 바이러스는 활성화된 바이러스와 닿으면 활성화 된다.
  • 빈칸은 활성화된 바이러스와 닿으면 활성화된 바이러스가 있는곳으로 바뀐다.

해결 전략 (8)

  • 제한시간이 0.25초이다
    • 연구소를 전부 순회하여 바이러스 분포 상태를 확인하지 않는다.
    • 빈 공간의 개수를 미리 세어 놓고, 남은 빈공간의 개수만 확인한다.
  • 활성화할 바이러스를 뽑는 조합을 만든다.
  • 활성화된 바이러스를 BFS를 통해 퍼뜨린다.

설계, 구현 (17)

  • 비트 마스킹을 이용해 활성화할 바이러스 조합을 만든다.
  • 남은 빈 공간을 확인한다.
  • 모두 바이러스를 채웠다면, 시간을 재보고 BFS를 끝낸다.
  • 아직 빈 공간이 남아 있다면 같은 시간대의 BFS를 묶어 진행한다.
  • 시간이 한번도 갱신 되지 않았다면, 모든 빈칸에 바이러스를 퍼뜨리는 것이 실패한 것이다.

주의할 점

  • 빈 칸에 바이러스를 다 뿌려보는 것이다.
  • 비 활성화 상태의 바이러스는 빈칸이 아니다.
  • 시간마다 동시에 바이러스가 퍼져나간다.

디버깅 (30)

  • 빈 칸을 바이러스로 채우는 것인데, 활성화까지 시키는 것으로 잘못 읽었다.
  • 모든 빈칸을 전부 바이러스로 메꾼 경우, 종료 시키는 분기문의 위치를 잘못 놓았었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
#define pp pair<int, int>
#define x first
#define y second

using namespace std;

queue<pp> q;
vector<pp> ready_virus;
vector<int> run_virus;

int board[52][52];
bool visit[52][52];

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

int n, m;
int empty_space;
int virus_num;

int answer = INT_MAX;

void Bfs() {

    int left_space = empty_space;
    int _time = 0;

    while (!q.empty()) {

        if (left_space == 0) {
            answer = min(answer, _time);
            return;
        }

        int q_size = q.size();
        while (q_size--) {
            auto cur = q.front(); q.pop();

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

                if (nx < 0 or nx >= n or ny < 0 or ny >= n) continue;
                if (visit[nx][ny] or board[nx][ny] == 1) continue;

                if (board[nx][ny] == 0) left_space--;
                visit[nx][ny] = true;
                q.push({ nx,ny });
            }
        }
        _time++;
    }
}


void Solve() {
    do {

        q = queue<pp>();
        memset(visit, false, sizeof(visit));

        for (int i = 0; i < virus_num; ++i) {

            if (run_virus[i] == 0) continue;

            auto running_virus = ready_virus[i];
            visit[running_virus.x][running_virus.y] = true;
            q.push({ running_virus.x, running_virus.y });
        }

        Bfs();

    } while (prev_permutation(run_virus.begin(), run_virus.end()));

    if (answer == INT_MAX) cout << -1 << "\n";
    else cout << answer << "\n";
}

void Make_Bitmask() {
    for (int i = 0; i < m; ++i) {
        run_virus.push_back(1);
    }

    for (int i = 0; i < virus_num - m; ++i) {
        run_virus.push_back(0);
    }
}

void Input() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cin >> board[i][ii];
            if (board[i][ii] == 0) empty_space++;
            if (board[i][ii] != 2) continue;
            
            ready_virus.push_back({ i,ii });
        }
    }

    virus_num = (int)ready_virus.size();
    Make_Bitmask();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    
    Input();
    Solve();

    return 0;
}

피드백

  • 완벽하게 문제를 이해했다고 생각해도 아닌 경우가 많다.
  • 예제도 대충 보고 넘기지 말고 꼼꼼히 보고 가자.
  • 문제에서 요구하는 것을 한 줄로 정확하게 정리하는 연습을 하자.