[백준] 17142 - 연구소3

이것 또한 삼성전자 기출이라고 한다

그냥 BFS라고 생각해서 풀었다가 예외처리를 겁나 해준.....

dfs와 함께 섞어서 사용하지만, 메인은 bfs라서 bfs에 올림

최적화나 코드 정리따위는 하고 싶지않아서 그냥 간단하게 코드정리만 하고 포스팅

1. 언제나 그렇든 map을 입력을 받는다

- 입력을 받으며 바이러스는 따로 구조체배열에 저장하고, 벽과 바이러스가 없는 구간의 공간을 count해준다

2. dfs를 돌면서 virus를 M개만큼 선택하며 큐에 담아준다

3. bfs에 들어가면, 큐에 담긴 K개의 좌표를 visit배열에 표기하고, st값을 올려주면서 virus(순회한 virus로 정의했음)의 갯수를 올림

4. bfs를 돌면서 조건에 맞게 단순 bfs를 돌지만, virus가 있는 공간을 지날때, map[ny][nx] = 0인 지점을 지날때를 각각 count

5. 가장 마지막의 지점의 시간을 찾은 후, visit배열을 순회하며, 같은 시간에 virus가 아닌 지점이 있다면 bool로 check하고 break걸고 빠져나옴

6. 마지막 시간에 도착한 점이 virus만 있다면, -2, 아니라면 -1만 해주고 return하면 될 것으로 보이나, 모두 바이러스가 못퍼지는 경우가 있다.

- 이때 virus를 순회한 곳과, free space를 순회한 것이 입력받으며 count한 것과 다를 때, INF로 큰값을 반환하고, 같다면 찾은 시간을 return한다

7. return받은 값이 작은 값인지 확인하여 갱신, 위의 과정을 반복한다.

8. 모든 과정이 끝났을 때, dab이 INF일 경우 -1, freespace가 0이었을 경우 0으로 출력하고, 그 외에는 찾은 dab을 출력한다.

뭔가 효율적으로 코드를 짤 수 있었을 것 같지만...... 귀찮다...... 뭐...... 못하는 것일 수도 있지만......

#include <iostream>
#define MXSIZE 51
#define INF 987654321
using namespace std;
 
struct QUEUE {
    int x, y;
}q[MXSIZE * MXSIZE], arr[11];
 
int map[MXSIZE][MXSIZE];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int N, K, dab = INF, cnt, space;
 
int bfs(){
    int visit[MXSIZE][MXSIZE] = { 0, };
    int st, ed, ix, iy, nx, ny;
    int check_space = 0, virus_cnt = 0;
    st = ed = -1;
    for (int i = 0; i < K; i++) {
        visit[q[i].y][q[i].x] = 1;
        ++st; virus_cnt++;
    }
    while (st != ed) {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++) {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[ny][nx] || map[ny][nx] == 1) continue;
            if (map[ny][nx] == 2) { virus_cnt++; }
            if (map[ny][nx] == 0) { check_space++; }
            q[++st].x = nx; q[st].y = ny; visit[ny][nx] = visit[iy][ix] + 1;
        }
    }
    bool check_end_virus = true;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j] == visit[q[ed].y][q[ed].x] && map[i][j] == 0) {
                check_end_virus = false;
                break;
            }
        }
        if (!check_end_virus) break;
    }
 
    int ret = check_end_virus ? visit[q[ed].y][q[ed].x] - 2 : visit[q[ed].y][q[ed].x] - 1;;
    ret = check_space + virus_cnt == space + cnt ? ret : INF;
    return ret;
}
 
void dfs(int d, int pos) {
    if (d == K) {
        int tmp = bfs();
        dab = dab > tmp ? tmp : dab;
        return;
    }
    for (int i = pos; i < cnt; i++) {
        q[d] = arr[i];
        dfs(d + 1, i + 1);
    }
}
 
int main(void) {
    
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j]; 
            if (map[i][j] == 2) { arr[cnt].x = j; arr[cnt++].y = i; }
            if (!map[i][j]) space++;
        }
    }
 
    dfs(0, 0);
 
    dab = dab == INF ? -1 : dab;
 
    if (space == 0) dab = 0;
 
    cout << dab << endl;
 
    return 0;
}