[PS] 백준 1600번: 말이 되고픈 원숭이

|

문제

내가 이해한 문제 내용

말이 이동하는 것처럼 8방향으로 이동 할 수 있고 상하좌우 4방향으로 이동할 수 있다. 하지만 말처럼 이동하는 횟수는 제한이 있을 때 (0,0)에서 (h,w)로 가는 최단경로를 구하시오.

접근 방식

BFS쓰면 바로 풀릴 줄 알았으나 벽 부수고 이동하기 문제처럼 상태값을 저장해야 하는 트릭이 있었다. 그래서 visit 배열을 3차원으로 만들어서 “현재까지 말처럼 이동한 횟수”를 추가해주었다.

어려웠던 점 & 배운 점

이 테크닉 문제를 2번째 풀었는데 바로 캐치하지 못한점이 아쉽고 TC를 자체적으로 만들지 못한 점을 개선해야겠다고 생각한다.

시간복잡도

방향이 12방향인데 상수이고 최악의 경우 $W\times H$를 모두 탐색해야 하므로 $O(WH)$

코드

#include <cstdio>
#include <queue>

struct monkey{
    int x;
    int y;
    int num;
    int knum;
};

std::queue<monkey> q;

int k,w,h,_x,_y,_num,_knum;
int a[201][201];
int visit[201][201][30];

int kx[8] = {-2,-2,-1,1,2,2,-1,1};
int ky[8] = {-1,1,2,2,-1,1,-2,-2};
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int bfs(int x, int y)
{
    q.push({x,y,0,0});
    visit[0][0][0] = 1;

    while(!q.empty()){
        monkey m = q.front();
        _x = m.x, _y = m.y, _num = m.num, _knum = m.knum;
        if(_x==h-1 && _y==w-1) break;
        q.pop();
        if(_knum < k){
            for(int i=0; i<8; i++){
                int _kx = _x+kx[i], _ky = _y+ky[i];
                if(_kx<0 || _kx>=h || _ky<0 || _ky>=w) continue;
                if(a[_kx][_ky]==1 || visit[_kx][_ky][_knum+1]) continue;
                visit[_kx][_ky][_knum+1] = 1;
                q.push({_kx,_ky,_num+1,_knum+1});
            }
        }
        for(int i=0; i<4; i++){
            int _dx = _x+dx[i], _dy = _y+dy[i];
            if(_dx<0 || _dx>=h || _dy<0 || _dy>=w) continue;
            if(a[_dx][_dy]==1 || visit[_dx][_dy][_knum]) continue;
            visit[_dx][_dy][_knum] = 1;
            q.push({_dx,_dy,_num+1,_knum});
        }
    }
    return q.size() ? _num : -1;
}


int main(void)
{
    scanf("%d%d%d",&k,&w,&h);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            scanf("%d",&a[i][j]);
        }
    }

    printf("%d",bfs(0,0));
    return 0;
}