[백준 17141번] 연구소 2

문제 링크: https://www.acmicpc.net/problem/17141

17141번: 연구소 2

<문제 풀이> 조합, BFS, 시뮬레이션

선택 가능한 바이러스 중에서 M개를 뽑는 조합을 구현하고 BFS로 바이러스를 퍼뜨리면 됩니다.

이때  2차원 배열의 각 원소의 인덱스를 0, 1, 2, 3... (N * N)이라고 생각하면 1차원 배열에서의 조합과 마찬가지로 조합 알고리즘을 적용할 수 있습니다.

그리고 이 인덱스를 이용해서 2차원 배열의 좌표를 다음과 같이 구할 수 있습니다.

x = i % N
y = i / N 

 

 

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
 
#define X first
#define Y second
#define SELECTABLE 2 //바이러스로 뽑을 수 있는 경우
#define VIRUS -1 // 바이러스로 뽑은 경우
#define WALL 1 // 벽
#define EMPTY 0 //빈 칸
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
int N, M;
int board[50][50];
int visited[50][50];
int res = -1;
 
 
void dfs(int idx, int cnt) {
    if (cnt == M) {  //바이러스를 M개 뽑으면 
        fill(&visited[0][0], &visited[49][50], -1);
        queue<pair<int, int> > Q;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == VIRUS) {
                    Q.push({ i, j });
                    visited[i][j] = 0;
                }
            }
        }
        //바이러스 퍼뜨리기
        while (!Q.empty()) {
            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 || ny < 0 || nx >= N || ny >= N)continue;
                if (board[nx][ny] == WALL || board[nx][ny] == VIRUS) continue;
                Q.push({ nx, ny });
                board[nx][ny] = VIRUS;
                visited[nx][ny] = visited[cur.X][cur.Y] + 1;
                
            }
        }
        int tempRes = -1;
        //바이러스를 모두 퍼트렸을 때
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == WALL) continue; //벽은 무시
                if (board[i][j] == EMPTY) return; //하나라도 퍼트리지 못했으면 -1
                tempRes = max(tempRes, visited[i][j]); // 퍼진 시간 갱신
            }
 
        }
        if (res == -1) res = tempRes; // 처음 갱신
        else res = min(res, tempRes); //가장 최소인 시간
        return;
    }
    int temp[50][50];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++){
            temp[i][j] = board[i][j];
        }
    }
    for (int i = idx; i < N * N; i++) {
        int x = i / N;
        int y = i % N;
        if (board[x][y] == SELECTABLE) { //바이러스로 선택 가능하면
            board[x][y] = VIRUS; // 바이러스로 선택
            dfs(i + 1, cnt + 1);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++)
                    board[i][j] = temp[i][j];
            }
        }
 
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
 
    dfs(0, 0);
 
    cout << res;
    
 
    return 0;
}