[9376] 탈옥

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

9376번: 탈옥

<문제>

상근이, 죄수1, 죄수2를 시작으로하는 bfs를 3번 수행한다.

3개의 bfs에 대해서, 모든정점까지의 최단경로를 전부 dist[][]에 저장해두고, 3번동안 전부 누적해준다.

단, 문은 한번만 열면 되므로 문이 존재하는 위치라면 -2를 해두어야 한다.

이후에는 dist[][]의 최소값을 찾아 출력하면 되는 문제이다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int t, n, m;
char s[104][104];
int dist[104][104][3], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
vector<pair<int, int>> start;
void f(int sy, int sx, int k) {
    deque<pair<int, int>> q;
    q.clear();
    q.push_back({sy, sx});
    dist[sy][sx][k] = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop_front();
        for (int i = 0; i < 4; i++) {
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 0 || x < 0 || y > n + 1 || x > m + 1) continue;
            if (dist[y][x][k] != -1 || s[y][x] == '*') continue;
            if (s[y][x] == '#') {
                dist[y][x][k] = dist[cur.first][cur.second][k] + 1;
                q.push_back({y, x});
            } else if (s[y][x] == '.' || s[y][x] == '$') {
                dist[y][x][k] = dist[cur.first][cur.second][k];
                q.push_front({y, x});
            }
        }
    }
}
int main(void) {
    int i, j;
    cin >> t;
    while (t--) {
        memset(s, 0, sizeof(s));
        cin >> n >> m;
        memset(dist, -1, sizeof(dist));
        start.clear();
        for (i = 0; i <= n + 1; i++) {
            for (j = 0; j <= m + 1; j++) {
                if (i == 0 || j == 0 || i == n + 1 || j == m + 1) {
                    s[i][j] = '.';
                    continue;
                }
                cin >> s[i][j];
                if (s[i][j] == '$') start.push_back({i, j});
            }
        }
        f(0, 0, 0);
        f(start[0].first, start[0].second, 1);
        f(start[1].first, start[1].second, 2);
        /*
        for (i = 0; i <= n + 1; i++) {
            for (j = 0; j <= m + 1; j++) {
                printf("%2d ", dist[i][j][0]);
            }
            cout << '\n';
        }
        */
        int ans = 987654321;
        for (i = 0; i <= n + 1; i++) {
            for (j = 0; j <= m + 1; j++) {
                if (s[i][j] == '.' || s[i][j] == '$' || s[i][j] == '#') {
                    int temp = 987654321;
                    if (dist[i][j][0] == -1 || dist[i][j][1] == -1 ||
                        dist[i][j][2] == -1)
                        continue;
                    if (s[i][j] == '#') {
                        temp =
                            dist[i][j][0] + dist[i][j][1] + dist[i][j][2] - 2;
                    } else {
                        temp = dist[i][j][0] + dist[i][j][1] + dist[i][j][2];
                    }
                    ans = min(temp, ans);
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
 

로직은 그리 어렵지 않은데, 구현이 어려웠다. 실수도 꽤 많이했던 문제인데...

 

1. bfs에서 방문처리를 dist[][]로 구분하면서, 동시에 이를 누적하여 최적해를 끌어내는 과정중

dist = -1로 초기화해두고 정답 탐색중

해당 정점을 방문하지 못하는데도 최적해를 구할때 참조하는 에러 -> 예외처리로 해결..

 

2. start를 매 테스트케이스마다 초기화하지 않은 실수

 

3. 0-1bfs를 몇문제 안풀어봐서 생긴것 같은, pop_front()를 pop_back()으로 적은 실수

 

거의 푸는데 2시간도 더걸렸다... 이정도나 걸릴 문제가 아닌데도 말이다