[백준-17836] 공주님을 구해라!

전형적인 BFS 문제이다.

단순히 길만 따라서 check 배열에 메모 후 탐색, 메모 후 탐색 의 로직으로 문제를 풀게 되면 틀리게 된다. 탐색하는 경우의 수가 사실 2배 더 많기 때문이다.

칼이 있는지, 없는지에 대한 경우를 생각해야 하기 때문에 2배이다. 예를 들어 (2,3) 위치에 이동할 때, 칼을 가진 상태로 이동하는 것과 칼을 가지지 않은 상태로 이동하는 것은 명백히 다른 경우의 수이다. 떄문에 이 두 가지 경우를 다르게 봐야하고 그에 따라 check배열 또한 3차원 배열로 만들어주어야 한다. 그 후에는 다음 코드와 같이 단순히 BFS 탐색을 때리면 끝!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

#define INF 10000000

using namespace std;
typedef pair<int, int> pii;

struct Move {
    int x, y, tm;
    bool sword;
};
Move initMove(int _x, int _y, int _tm, bool _s) {
    Move m;
    m.x = _x;
    m.y = _y;
    m.tm = _tm;
    m.sword = _s;
    return m;
}

int arr[101][101];
int check[101][101][2];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

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

    int n, m, t;
    cin >> n >> m >> t;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    queue<Move> q;
    q.push(initMove(1, 1, 0, false));
    check[0][0][0] = 1;
    int min_time = INF;

    while (!q.empty()) {
        Move cur = q.front();
        q.pop();
        if (cur.tm > t) continue;
        if (cur.x == n && cur.y == m) {
            min_time = min(min_time, cur.tm);
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int cx = cur.x + dx[i];
            int cy = cur.y + dy[i];
            if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
            
            if (cur.sword == false) { // 1. 아직 칼을 못찾은 경우
                if (check[cx][cy][0]) continue;
                if (arr[cx][cy] == 1) {
                    continue;
                }
                else if (arr[cx][cy] == 2) { // 1.1. 칼을 찾은 경우
                    check[cx][cy][0] = 1;
                    q.push(initMove(cx, cy, cur.tm + 1, true));
                }
                else if (arr[cx][cy] == 0) { // 1.2. 그냥 길인 경우
                    check[cx][cy][0] = 1;
                    q.push(initMove(cx, cy, cur.tm + 1, false));
                }
            }
            else if (cur.sword == true) { // 2. 칼을 찾은 경우
                if (check[cx][cy][1]) continue;
                check[cx][cy][1] = 1;
                q.push(initMove(cx, cy, cur.tm + 1, true));
            }
        }

    }
    if (min_time == INF)
        cout << "Fail";
    else
        cout << min_time;

    return 0;
}

 

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

17836번: 공주님을 구해라!