[백준_17142(연구소3)]

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

17142번: 연구소 3

문제 설명

• 첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
• 둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
• 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

문제 풀이

• char p[55][55] : 입력받은 숫자 판을 문자로 변경한 배열 (벽 =>'-' ,빈 공간 => '0',바이러스 =>'*')
• int visited[55][55] : BFS를 돌면서 소요되는 시간 및 방문을 나타태는 배열
• 총 바이러스가 10개 이다. 10개 중 M개를 골라 모든 경우를 다 탐색할 시간이 충분하다.
• next_permutation을 사용하여 10개 중 M개를 고르고 queue 에 넣는다.
• BFS로 연구소를 돌면서 벽일 경우를 제회하고는 모두 순회 한다.
  • 비활성화 => 활성화 되어도 시간초는 지장이 없다.
• 모두 순회 한 이후에 visited를 탐색하면서 방문 하지 않고 벽이 아닌 곳(0)이 있는지 탐색한다.
  • 만일 있다면 , 전파 실패로 판단
  • 방문했고 이미 바이러스가 아닌 지점의 최댓값을 저장한다.
• 전파 실패가 아닐 경우의 최소값들을 구한다.
• -1을 기준으로 할때, min이나 max 내장 함수를 사용하기보단 if (ans == -1 || temp < ans) 조건문을 사용해야 실수를 잡을 수 있다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

char p[55][55]; //입력 받은 숫자가 문자로 변경 된 판

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

int main()
{

    cin >> n >> m;

    vector<pair<int, int> > virus;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int x;
            cin >> x;
            if (x == 2)
            {
                p[i][j] = '*';
                virus.push_back(make_pair(i, j)); //바이러스 위치를 저장
            }
            else if (x == 1)
            {
                p[i][j] = '-';
            }
            else
            {
                p[i][j] = '0';
            }
        }
    }

    vector<int> selected; //조합으로 활성화 바이러스 위치를 선택 위한 배열

    for (int i = 0; i < virus.size() - m; i++)
    {

        selected.push_back(0);
    }

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

        selected.push_back(1);
    }
    int ans = -1;

    do
    {

        queue<pair<int, int> > q;
        int visited[55][55];
        memset(visited, -1, sizeof(visited));

        for (int i = 0; i < virus.size(); i++)
        {

            if (selected[i]) //선택된 인덱스의 저장된 좌표값의 바이러스 활성화
            {
                int x = virus[i].first;
                int y = virus[i].second;
                q.push(make_pair(x, y));
                visited[x][y] = 0;
            }
        }

        while (!q.empty()) //BFS
        {

            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 (nx < 0 || nx >= n || ny < 0 || ny >= n)
                    continue;

                if (p[nx][ny] == '-') //벽
                    continue;
                if (visited[nx][ny] != -1) //이미 방문
                    continue;

                if (p[nx][ny] == '0') //빈공간
                {
                    visited[nx][ny] = visited[x][y] + 1;
                }
                else if (p[nx][ny] == '*') //비활성화 된 곳이어도 똑같이 진행
                {
                    visited[nx][ny] = visited[x][y] + 1;
                }
                q.push(make_pair(nx, ny));
            }
        }

        bool result = true; // 실패여부 판단 변수
        int temp = 0;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {

                if (visited[i][j] == -1 && p[i][j] == '0') //방문하지 않았고 빈공간인 경우
                {

                    result = false;
                    break;
                }
                else if (visited[i][j] != -1 && p[i][j] != '*') //방문 했으면서 바이러스가 아닌 경우 (요구 조건이 바이러스 모두 퍼진 최소 값이기 때문)
                {

                    temp = max(temp, visited[i][j]); //최대로 걸린 시간 뽑아냄
                }
            }
        }

        if (result) //전파 실패가 아닐 경우 최솟값구하기
        {
            if (ans == -1 || temp < ans)
            {
                ans = temp;
            }
        }

    } while (next_permutation(selected.begin(), selected.end())); //조합

    cout << ans << '\n';

    return 0;
}