17141 - 연구소 2

문제 풀이

N,M의 범위가 작으므로 브루트 포스를 이용하여 풀었다.
로직은 어렵지 않으나 구현부분에서 생각할 부분이 많은 문제

---

기본 로직

1. 백트래킹을 이용하여 바이러스를 놓을 수 있는 모든 경우를 선택
2. M개가 선택되면 bfs를 이용하여 바이러스를 퍼트림
   visited를 이용하여 방문한 경우에도 dist보다 작은 거리이면 방문할 수 있다.
3. 바이러스가 퍼지는 최소시간을 저장
4. 모든 경우에 대해 2, 3번을 수행

---

첫번째 풀이

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

int N, M;
int map[51][51];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
vector<pair<int, int>> v;
int dist[51][51];
int ans=1000000000;
bool visited[51][51];

void bfs(int startX, int startY) {
    queue<pair<int, int>> q;
    visited[startX][startY] = true;
    dist[startX][startY] = 0;
    q.push({ startX, startY });
    while (!q.empty()) {
        int c_x=q.front().first;
        int c_y=q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int n_x = c_x + dx[i];
            int n_y = c_y + dy[i];
            if (map[n_x][n_y]!=1  && n_x >= 1 && n_y >= 1 && n_x <= N && n_y <= N) {
                if (visited[n_x][n_y]) {
                    if (dist[n_x][n_y] > dist[c_x][c_y] + 1) {
                        dist[n_x][n_y] = dist[c_x][c_y] + 1;
                        q.push({ n_x, n_y });
                    }
                }
                else {
                    dist[n_x][n_y] = dist[c_x][c_y] + 1;
                    q.push({ n_x, n_y });
                    visited[n_x][n_y] = true;

                }
            }

        }
    }
}

void pick(int n) {
    if (n == M) {
        for (int i = 0; i < v.size(); i++) {
            bfs(v[i].first, v[i].second);
        }

        int tmp = 0;
        for (int i = 1; i <= N; i++) {
            if (tmp == -1) { break; }
            for (int j = 1; j <= N; j++) {
                if ( map[i][j]!=1 && tmp<dist[i][j]) {
                    tmp = dist[i][j];
                }
                if (map[i][j] == 0 && !visited[i][j]) {
                    tmp = 1000000000;
                    break;
                }
            }
        }
       
        if (ans > tmp) { ans = tmp; }

        memset(visited, 0, sizeof(visited));
        memset(dist, 0, sizeof(dist));
        return;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j] == 2) {
                map[i][j] = 0;
                v.push_back({ i,j });
                pick(n + 1);
                v.pop_back();
                map[i][j] = 2;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    pick(0);

    if (ans == 1000000000) {
        ans = -1;
    }
    cout << ans;
    return 0;
}

시간초과!
pick함수 퍼질 수 있는 바이러스를 고르는 과정에서 예를들어 1~4중에 3개를 고른다고하면

• 잘못된 경우
  123
  213
  321
  ...
  이런식으로 순서가 다르면 다른 것으로 취급하여 같은 경우에도 계산을 해주어 시간 낭비하고 있었다.

• 올바른 경우
  123
  124
  134
  234

pick함수의 중복되는 경우를 바꿔주었다.

정답 코드

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

int N, M;
int map[51][51];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
vector<pair<int, int>> v;
int dist[51][51];
int ans=1000000000;
bool visited[51][51];
bool check[51][51];

void bfs(int startX, int startY) {
    queue<pair<int, int>> q;
    visited[startX][startY] = true;
    dist[startX][startY] = 0;
    q.push({ startX, startY });
    while (!q.empty()) {
        int c_x=q.front().first;
        int c_y=q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int n_x = c_x + dx[i];
            int n_y = c_y + dy[i];
            if (map[n_x][n_y]!=1  && n_x >= 1 && n_y >= 1 && n_x <= N && n_y <= N) {
                if (visited[n_x][n_y]) {
                    if (dist[n_x][n_y] > dist[c_x][c_y] + 1) {
                        dist[n_x][n_y] = dist[c_x][c_y] + 1;
                        q.push({ n_x, n_y });
                    }
                }
                else {
                    dist[n_x][n_y] = dist[c_x][c_y] + 1;
                    q.push({ n_x, n_y });
                    visited[n_x][n_y] = true;

                }
            }

        }
    }
}

void pick(int n,int x, int y) {
    if (n == M) {
        for (int i = 0; i < v.size(); i++) {
            bfs(v[i].first, v[i].second);
        }

        int tmp = 0;
        for (int i = 1; i <= N; i++) {
            if (tmp == -1) { break; }
            for (int j = 1; j <= N; j++) {
                if ( map[i][j]!=1 && tmp<dist[i][j]) {
                    tmp = dist[i][j];
                }
                if (map[i][j] != 1 && !visited[i][j]) {
                    tmp = 1000000000;
                    break;
                }
            }
        }
       
        if (ans > tmp) { ans = tmp; }

        memset(visited, 0, sizeof(visited));
        memset(dist, 0, sizeof(dist));
        return;
    }

    for (int i = x; i <= N; i++) {
        for (int j = y; j <= N; j++) {
            if (!check[i][j] && map[i][j] == 2) {
                map[i][j] = 0;
                v.push_back({ i,j });
                check[i][j] = 1;
                pick(n + 1, v[n].first, v[n].second);
                check[i][j] = 0;
                v.pop_back();
                map[i][j] = 2;
            }
        }
        y = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    pick(0,1,1);

    if (ans == 1000000000) {
        ans = -1;
    }
    cout << ans;
    return 0;
}

정답!