[BOJ] 33578 누가 이름 안 적고 나갔어

문제 요약

문제 링크: 백준 33578 - 누가 이름 안 적고 나갔어

문제 설명

---

접근 방법

처음엔 일반적인 방문처리 기반 BFS 문제로 접근해서 풀이했다. 하지만 계속 틀렸고 아래와 같은 반례를 만들 수 있었다. 

2 6
S....J
TTTTT.

 

답은 9가 나와야 한다. (0, 5) → (1, 5) → (1, 4) → (1, 3) → (1, 2) → (1, 1) → (1, 0) → (0, 0)

일반 방문처리 기반 BFS로 구현한다면, 큐는 걸음 횟수가 아닌 이동 횟수 자체가 적은 순서대로 작동하기에 문제에서 요구하는 최소 걸음 횟수를 구할 수 없게 되는 것이 그 이유이다.

 

따라서 이 문제에선 SPFA(Shortest Path Faster Algorithm) 알고리즘을 적용해서, 방문처리가 된 장소라 하더라도 더 빠른 걸음 횟수에 도달했다면 새롭게 탐색하는 방식으로 구현했다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, sy, sx, ey, ex, ans = 1e9;
char mat[3001][3001];
int vis[3001][3001][2];
int d[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

void solve() {
    queue<tuple<int, int, int, bool>>q;
    q.push({ sy,sx,0,false });
    vis[sy][sx][0] = 1;
    while (q.size()) {
        int y = get<0>(q.front());
        int x = get<1>(q.front());
        int t = get<2>(q.front());
        bool jinwoo = get<3>(q.front());  // 진우면 0, 선생님이면 1
        q.pop();    
        if (vis[y][x][jinwoo] < t)  // SPFA 거리 기반 갱신 가능 여부
            continue;
        if (y == ey && x == ex) {
            ans = min(ans, t);
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int yy = y + d[i][0];
            int xx = x + d[i][1];
            if (yy >= n || yy < 0 || xx >= m || xx < 0) continue;
            if (mat[yy][xx] == '#') continue;
            if (!jinwoo) {
                if (mat[yy][xx] == 'T') {
                    if (vis[yy][xx][1] <= t + 2) continue;
                    q.push({ yy,xx,t + 2,true });
                    vis[yy][xx][1] = t + 2;
                }
                if (vis[yy][xx][0] <= t + 2) continue;
                q.push({ yy,xx,t + 2,false });
                vis[yy][xx][0] = t + 2;
            }
            else {
                if (vis[yy][xx][1] <= t + 1) continue;
                q.push({ yy,xx,t + 1,true });
                vis[yy][xx][1] = t + 1;
            }
        }
    }
    if (ans == 1e9) ans = -1;  // 찾을 수 없는 경우
    cout << ans;
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> mat[i];
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 'J') {
                sy = i;
                sx = j;
            }
            else if (mat[i][j] == 'S') {
                ey = i;
                ex = j;
            }
            vis[i][j][0] = 1e9;
            vis[i][j][1] = 1e9;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}