[BOJ 16137] 견우와 직녀

https://www.acmicpc.net/problem/16137 (견우와 직녀)

 이 문제는 N X N 크기의 지도에서 견우가 (0,0)에서 출발해 (N-1, N-1)까지 가는 최단경로를 구하는 문제이다. 다만 몇 가지 제약사항이 있다. 바로 까치와 까마귀가 오작교를 만들어줘야하는데 노령화(?)로 인해 직녀에게 가는 오작교를 한 번에 만들지 못한다. 그리고 만든다고 해도 지나갈 수 있는 시간이 정해져 있다.

맵은 모두 3가지의 숫자를 가진다.

0: 절벽

1: 견우가 지나갈 수 있는 곳

2 이상의 정수 : 이미 설치된 오작교, 정수는 오작교의 주기를 의미한다.

 만약, 주기가 3인 오작교를 까치와 까마귀가 만든다면 0분, 3분, 6분, 9분 ... 에는 지나갈 수 있고 나머지 시간인 1분 , 2분, 4분, 5분 ... 에는 지나갈 수 없다. 예제를 잘 보지 않으면 헷갈리기 쉬운게 오작교가 설치되어 있는 지점의 시간이 0분, 3분, 6분, 9분 ... 이어야 해당 점을 지나갈 수 있다. 즉, 오작교 지점을 방문하기 전 지점에서 2분, 5분, 8분 ... 이어야 오작교를 건널 때 3분, 6분, 9분이 되어 지나갈 수 있다. 0분도 지나갈 수 있게 만든 것은 처음에 출발하는 지점인 (0,0)이 2이상의 정수일 경우 기다리지 않고 바로 출발할 수 있도록 만들어둔 듯하다.

 또하나의 조건이 있는데, 이미 설치되어있는 오작교 말고도 추가적으로 M의 주기값을 가진 오작교 하나를 절벽에 설치해서 지나갈 수 있다. 단, 오작교를 두 번 연속 지나갈 수 없다.(두 번연속으로 지나가면 견우가 더 이상 이동할 수 없는 현상이 생길 수 있기 때문이라고 한다.) 이 제약 조건 때문에 2시간 넘게 틀린 곳을 찾았던 것 같다. 그리고 오작교를 설치할 수 있는 절벽은 절벽의 교차점이 아닌 곳에 가능하다. (문제 참조)

문제 풀이 : bfs를 이용해서 최단 거리를 찾았다. 오작교를 건너기 전에 건널 수 있는 시간인지를 확인하여 건너지 못할 경우 시간을 증가시키고 다시 큐에 집어 넣었다. 그리고 오작교를 2번 연속으로 건너지 않아야 한다. 가만히 생각해보면 오작교가 설치되는 지점은 교차점이 아니기 때문에 오작교를 건너고나서 움직이는 방향은 오작교를 건널때의 방향과 일치한다. 따라서 오작교를 건널 때 다음으로 갈 지점도 한 번 확인해서 그 부분이 1이 아니라면 갈 수 없는 곳이 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int N, M;
int ans;
int visit[11][11];
bool check(vector <vector <int> > &map, int x, int y) {
    int xc=0, yc = 0;
 
    for (int i = 0; i <2; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
 
        if (map[nx][ny] == 0) xc++;
    }
 
    for (int i = 2; i <4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
 
        if (map[nx][ny] == 0) yc++;
    }
 
    if (xc >= 1 && yc >= 1) return false;
 
    return true;
}
 
void bfs(vector <vector <int> > &map, queue<tuple<int, int, int> > &q) {
 
    while (!q.empty()) {
        int x, y, time;
        tie(x, y, time) = q.front();
 
        if (x == N - 1 && y == N - 1) {
            if (ans > time) ans = time;
            return;
        }
        q.pop();
        bool wait = false;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (map[nx][ny] == 0) continue;
            if (visit[nx][ny]) continue;
 
 
            if (map[nx][ny] == 1) {
                visit[nx][ny] = 1;
                q.push(make_tuple(nx, ny, time + 1));
            }
 
            if (map[nx][ny] > 1) {
                int remain = time % map[nx][ny];
                if (remain != map[nx][ny] - 1) {
                    wait = true;
                }
                else {
                    int nnx = nx + dx[i];
                    int nny = ny + dy[i];
                    
                    if (nnx < 0 || nnx >= N || nny < 0 || nny >= N) continue;
                    if (map[nnx][nny] != 1) continue;
 
                    visit[nx][ny] = 1;
                    q.push(make_tuple(nx, ny, time + 1));
                }
            }
        }
        if (wait) { q.push(make_tuple(x, y, time + 1)); }
    }
}
int main() {
    
        cin >> N >> M;
 
        vector <vector <int> > map(N, vector<int>(N));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        ans = 987654321;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0 && check(map, i, j)) {
                    memset(visit, 0, sizeof(visit));
                    queue<tuple<int, int, int> > q;
                    q.push(make_tuple(0, 0, 0));
                    visit[0][0] = 1;
                    map[i][j] = M;
                    bfs(map, q);
                    map[i][j] = 0;
                }
            }
        }
 
        cout << ans << '\n';
    
    return 0;
}