백준 1600번. 말이 되고픈 원숭이(c++) / BFS

방문처리가 핵심인 BFS문제였다.

그냥 (x, y)로만 방문처리를 해주면, 더 빠른 길인데도 불구하고 누락되는 경우가 생긴다.

따라서, 말로 몇 번 이동했는지를 인자값으로 하나 더 넣어주었다. => visited[x좌표][y좌표][말 이동 횟수]

 

// 말이 되고픈 원숭이
#include <iostream>
#include <queue>
#include <tuple>
 
using namespace std;
 
int k, w, h;
int chess[201][201] = {0, };
int hx[8] = {-2, -1, 2, 1, 2, 1, -1, -2};
int hy[8] = {1, 2, 1, 2, -1, -2, -2, -1};
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
 
int move()
{
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(0, 0, 0, 0));
    int visited[201][201][31] = {0, };
 
    while(!q.empty()){
        int x, y, cnt, horseMove;
        tie(x, y, cnt, horseMove) = q.front();
        visited[x][y][horseMove] = true;
        q.pop();
 
        if(x==h-1 && y==w-1){
            return cnt;
        }
 
        if(horseMove+1<=k){
            for(int i=0; i<8; i++){
                int nx = x+hx[i];
                int ny = y+hy[i];
                if(0<=nx && nx<h && 0<=ny && ny<w && !visited[nx][ny][horseMove+1]){
                    if(chess[nx][ny]==0){
                        visited[nx][ny][horseMove+1] = true;
                        q.push(make_tuple(nx, ny, cnt+1, horseMove+1));
                    }
                }
            }            
        }
 
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0<=nx && nx<h && 0<=ny && ny<w && !visited[nx][ny][horseMove]){
                if(chess[nx][ny]==0){
                    visited[nx][ny][horseMove] = true;
                    q.push(make_tuple(nx, ny, cnt+1, horseMove));
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    cin>>k>>w>>h;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>chess[i][j];
        }
    }
 
    cout<<move()<<"\n";
    return 0;
}