백준[17142] 연구소 3 (add. 연구소 2)

이 문제의 출처는 아래와 같다. 참고로 '연구소2'와 매우 비슷하다.

 

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

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

 

 

먼저 이문제를 푸는데 필요한 것은 '조합' 을 먼저 작성하고 'BFS 탐색' 을 실시하여 탐색시 문제의 조건에 맞게 구현하면 해결할 수 있다.

 

 

먼저 입력을 받고 '조합'을 생각하자.

이 문제에서는 바이러스의 전체갯수 중에서 몇개를 선택하기 때문에, 바이러스의 위치를 저장한 vector를 DFS를 통해 조합을 구현하였다.

 

DFS 함수에서 골라야 하는 갯수를 모두 선택하였으면 그 떄, BFS를 시작하면된다.

처음 시작할때, 시작하는 바이러스를 모두 큐에 넣어주고

-1로 초기화된 방문여부 확인값을 0으로 만들어준다.

 

이제 BFS를 돌리면서 필자는 visit2[][] 배열에 이동한 시간들을 기록하였다. 종료조건이 전체 빈 공간이 모두 차야할때 끝이 나야하기 때문에 그것을 체크하기 위해 방문했으면 num을 증가시켜 방문한 곳의 수를 갱신하였다.

 

Max값은 바이러스가 이동한 시간들 중 가장 큰값으로 답변수 ans와 비교하여 모든 경우에따라 갱신하도록 지정하였다.

 

그렇다면 여기서 '연구소 2' 와 이 문제에서의 차이점은 단 1하나의 라인을 수정해서 해결할 수 있다.

연구소 3 에서는 방문한 곳이 바이러스라면 해당 바이러스를 활성화시켜 큐에 넣어줘야 한다.

 

그것은 46번쨰 라인에서 방문한곳이 빈공간이라면 이동한 시간의 최대값을 그대로 갱신하면서 가고 그렇지 않고 바이러스라면 Max값을 갱신하지 않은채 그대로 큐에 넣어 BFS를 계속 실행하면 된다.

 

코드는 아래와 같으며 주석으로도 간단하게 정리하였다.

 

 

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<iterator>
#include<deque>
#include<map>
 
using namespace std;
 
int n, m, dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 }, arr[55][55], visit[11];
int cnt, num, ans = 987654321, Max;
vector<pair<int, int>> v;
 
void bfs() {
    int visit2[55][55];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            visit2[i][j] = -1;
        }
    }
    queue<pair<int, int>> q;
    //cout << v.size() << endl;
    for (int i = 0; i < v.size(); i++) {
        if (visit[i] == 1) {
            q.push({ v[i].first,v[i].second });
            visit2[v[i].first][v[i].second] = 0;
        }
    }// 큐에 바이러스를 넣고 방문배열 초기화 
    //1이라는것은 해당 i번째 바이러스를 선택한것
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int kx = x + dx[i];
            int ky = y + dy[i];
            if (kx >= 0 && kx < n && ky >= 0 && ky < n) {
                if (visit2[kx][ky] == -1 && arr[kx][ky] != 1) {
                    visit2[kx][ky] = visit2[x][y] + 1;
                    if(arr[kx][ky] != 2) Max = max(Max, visit2[kx][ky]); // 바이러스가 아닌 곳에서만 visit2[][] 배열에 값 갱신
                    num++;
                    q.push({ kx,ky });
                }
            }
        }
    }// bfs 
    //
}
 
void dfs(int a, int b) {
    if (b == m) {
        bfs();
        if (cnt + v.size() == num + m) ans = min(ans, Max); // 모든 공간을 채웠을때 답을 갱신
        num = 0;
        Max = 0;
        //b == m 은 m개를 뽑았을때의 각 경우가 끝남
        // [1,1,1,0,0] 과 같은 경우 
        return;
    }
    for (int i = a; i < v.size(); i++) {
        visit[i] = 1;
        dfs(i + 1, b + 1);
        visit[i] = 0;
    } // dfs를 통한 조합
}
 
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 2) v.push_back({ i,j }) // 조합을 위해 바이러스의 위치를 저장
            if (arr[i][j] == 0) cnt++; // 빈 칸의 개수를 저장
        }
    }
    dfs(0, 0); //dfs시작
    if (ans == 987654321) printf("-1");
    else printf("%d", ans);
    return 0;
}