[1600번] 말이 되고픈 원숭이

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

BFS중 많이 까다로운 BFS인 것 같다.

원숭이는 앞, 뒤, 좌, 우 또는 말의 움직임 대로 움직일 수 있는데

만약 앞 뒤 좌 우 중 하나로 먼저 움직여서 visit배열을 1로 바꾼다면

차후에 말로 오는 방식으로 방문했는데 그때 visit가 이미 1이라서 못 방문할 수도 있는 상황이 생긴다.

2

5 3

0 0 0 0 0

1 0 1 1 0

1 0 1 1 0

이 코드를 보면 우, 우를 통해 0,2에 도달 할 수 있지만, (아래,아래,우) (위,위,우)를 통해서도 0,2를 갈 수 있다.

물론 이 방식에서는 같은 이동횟수로 왔기에 visit가 상관없지 않냐 생각 할 수 있지만, 저러한 모순이 생기기에

visit를 k번 썻을 때의 방문 횟수로 바꾸어 생각해야 한다.

visit[y][x][k] :: x,y 위치에 말처럼 이동할 수 있는 횟수가 k번 남았을 때 방문 여부

이렇게 하여 말처럼 이동 방식 그리고 기본 이동 방식 두개에 대해 판별하면 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   int arr[201][201]; bool visit[201][201][31];   int dxH[8] = { -2, -1, -2, -1, 1, 2, 1, 2 }; int dyH[8] = { -1, -2, 1, 2, -2, -1, 2, 1 }; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 };   typedef struct _MONKEY_ {     int x;     int y;     int cnt;     int k; }MONKEY;     int main() {     int k;     int w, h;     scanf("%d %d %d", &k, &w, &h);       for (int i = 0; i < h; i++)         for (int j = 0; j < w; j++)             scanf("%d", &arr[i][j]);       queue<MONKEY> q;       q.push({ 0,0,0,k});       while (!q.empty())     {         int x = q.front().x;         int y = q.front().y;         int cnt = q.front().cnt;         int k = q.front().k;           q.pop();                  if (visit[y][x][k] == 1)             continue;           visit[y][x][k] = 1;           if (x == w - 1 && y == h - 1)         {             printf("%d", cnt);             return 0;         }           // 나이트 이동 방식         for (int i = 0; i < 8; i++)         {             int hereX = x + dxH[i];             int hereY = y + dyH[i];             if (!k || hereX >= w || hereX < 0 || hereY >= h || hereY < 0 || visit[hereY][hereX][k - 1] || arr[hereY][hereX])                 continue;               q.push({ hereX, hereY, cnt + 1, k - 1 });         }           // 기본 이동 방식         for (int i = 0; i < 4; i++)         {             int hereX = x + dx[i];             int hereY = y + dy[i];             if (hereX >= w || hereX < 0 || hereY >= h || hereY < 0 || visit[hereY][hereX][k] || arr[hereY][hereX])                 continue;               q.push({ hereX, hereY, cnt + 1, k });         }     }       printf("-1");       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus