[BaekJoon] 1600 말이 되고픈 원숭이 :: monton

문제

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

풀이

가중치 없는 최소값을 구하는 문제이므로 bfs 사용

현재 위치의 x,y값과 말처럼 건넌 횟수를 담는 큐까지 총 3개의 큐 사용

한번 큐를 담을때 상하좌우 4번과 말이 갈 수 있는 위치 8개를 한번에 담는다

자꾸 틀려서 고생했는데 visitd[MAX][MAX][2]로 해주어서 말로 지나가지 않았을때와 말로 지났을때 이렇게 체크를 해주었다

하지만 다음과 같은 케이스에서 정확한 답을 낼 수 없다

2 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0

2 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0

2 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0

문제가 첫번째처럼 주어졌을 때 왼쪽 상단 검은색에서 오른쪽 하단 검은색으로 이동해야되는데

빨간색 경로처럼 이상적이다. 

파란색으로 이동하는 건 (0,0) -> (1,2) -> (1,3) -> (2,1) -> (2,2) -> (3,4) 로 이동하는 케이스 인데

만약 우선 순위에 의해 파란색 경로를 먼저 들려 visit[2][1][1]=true로 하였다면

보라색 위치에서 말의 방법으로 다시 방문하지 못하고 빨간색 경로로 시도 하지 못하게 될 것이다.

visitd[MAX][MAX][2]말고 visitd[MAX][MAX][31]로 바꾸어 주어야 한다

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int K, W, H,flag,ans;
int arr[201][201];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int dirh[8][2] = { {-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2} };
int visit[201][201][31];
 
int main() {
    cin >> K >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> arr[i][j];
        }
    }
    queue <int> qx, qy,qn;
    qx.push(0), qy.push(0), qn.push(0);
    visit[0][0][0] = 1;
 
    while (!qx.empty()) {
        int qsize = qx.size();
        while (qsize--) {
            int x = qx.front();
            int y = qy.front();
            int n = qn.front();
            qx.pop(),qy.pop(), qn.pop();
 
            if (x == H - 1 && y == W - 1) {
                flag = 1;
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
 
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (arr[nx][ny]) continue;
                if (visit[nx][ny][n]) continue;
                qx.push(nx), qy.push(ny), qn.push(n), visit[nx][ny][n] = 1;
            }    
 
            for (int i = 0; i < 8; i++) {
                int nx = x + dirh[i][0];
                int ny = y + dirh[i][1];
                int nn = n+1;
 
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (visit[nx][ny][nn]||arr[nx][ny]) continue;
                if (nn > K) continue;
 
                qx.push(nx), qy.push(ny), qn.push(nn), visit[nx][ny][nn] = 1;
            }
            
        }
        if (flag) break;
        ans++;
    }
    if (flag) cout << ans;
    else cout << "-1";
}