[C/C++] 백준 #1600 말이 되고픈 원숭이(너비 우선 탐색)

이번 문제는 너비 우선 탐색으로 풀었습니다.

 

그래프 이론 중에 프림 알고리즘, 다익스트라 알고리즘, 그리고 A* 알고리즘 모두 너비 우선 탐색(Bredth First Search)이 기초가 됩니다.

이 문제에서 너비 우선 탐색을 쓴 이유는 노드간의 간선의 값이 1이기 때문입니다.

 

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

1600번: 말이 되고픈 원숭이

 

그렇지만, 말(knight)의 이동이 k번으로 제한된다는 것때문에 별도의 자료를 사용해야 합니다.

 

일단 체스에서 말(knight)의 이동은 다음과 같습니다.

체스 나이트 이동

문제는 체스의 말 이동을 할 수 있는 제한이 k번이고, 인접칸으로의 이동은 무한하게 할 수 있습니다.

문제에서는 시작점에서 도착점까지 장애물로는 갈 수 없기 때문에 말 이동으로 넘어가거나 우회해서 가야합니다.

도착지점에 도달할 수 없는 경우에는 -1을 출력합니다.

 

일단 말의 이동을 쓴 경우라면, 보드상에 현재 말의 이동이 몇번 남았는지 표시토록 합니다.  BFS를 하다보면 더 적은 말의 이동을 소모한 경우가 있습니다.  그 경우에는 더 적은 말의 이동을 소모했으니, 그 값을 쓰고 진행하도록 합니다.  장애물 등의 이유로 말의 이동이 아니면 장애물을 넘을 수 없는 경우가 발생하기 때문입니다.  말의 이동횟수를 저장한 배열을 사용했으므로 방문했다는 것을 따로 표시할 필요는 없습니다.  말의 남은 이동횟수가 같은 경우에는 해당 이동은 이동횟수는 더 많고, 말의 이동횟수는 같으니, 그 이전에 값이 쓰여졌을 때가 더 먼저이기 때문입니다.

 

아래는 제가 작성한 소스입니다.  소스는 참조용으로만 봐주세요.

//----------------------------------------------------
//    baekjoon #1600 - A Monkey that want to a Horse
//        - by Aubrey Choi
//        - created at 2020-01-21
//----------------------------------------------------
#include <stdio.h>
#include <queue>

int k, w, h;
char map[200][200], v[200][200];
struct Node { int r, c, k, s; };
int main()
{
    int i, j, s; Node t, u;
    scanf("%d%d%d",&k,&w,&h);
    for(i=0;i<h;i++) for(j=0;j<w;j++)
    {
        scanf("%d",&s);
        map[i][j]=s;
        v[i][j]=-1;
    }
    std::queue<Node> q;
    t.r=0, t.c=0, t.k=k, t.s=0;
    q.push(t); v[0][0]=k;
    while(!q.empty())
    {
        u=q.front(); q.pop();
        if(u.r==h-1&&u.c==w-1) break;
        int d[][2]={-1,-2, -1,2, 1,-2, 1,2, -2,-1, -2,1, 2,-1, 2,1, 0,1, 1,0, 0,-1, -1,0};
        for(i=0;i<12;i++)
        {
            t.r=u.r+d[i][0], t.c=u.c+d[i][1], t.s=u.s+1, t.k=u.k-(i<8);
            if(t.r<0||t.r>=h||t.c<0||t.c>=w||map[t.r][t.c]||v[t.r][t.c]>=t.k) continue;
            v[t.r][t.c]=t.k;
            q.push(t);
        }
    }
    if(u.r==h-1&&u.c==w-1) printf("%d\n", u.s); else puts("-1");
}