[C언어] 1600. 말이 되고픈 원숭이

BFS의 방문 처리를 3차원으로 해줘야하는 문제.

2206번 벽 부수고 이동하기의 응용 버전이다. 딱히 큰 응용도 아님...

나는 벽을 만났을 때만, 말 처럼 움직인다고 생각하고 풀었는데....계속 틀리는거다!!!알고보니..벽에 상관없이 그냥 최단거리 구하는 문제였다..ㅜ,ㅠ

중요한건!!

방문 처리를 할 때, 말처럼 움직인 횟수에 따라 방문 처리하는 배열이 달라진다. 왜냐하면!! 방문 처리는 상하좌우 움직임과 함께 말처럼 움직일 때의 최단 거리를 위해서 하는 것이라, 같은 상태에서만 방문 처리를 해줘야 한다. 움직임은 말 처럼 움직이는 것에 제한을 받기 때문!!!

말 처럼 1번 뛰었는데 0번 뛴 방문 체크 배열에 방문 체크를 하면 안 된다. 서로 상태가 다를 때의 방문을 의미하기 때문..설명하기 어렵다. 왜냐하면 나도 이해한지 얼마 안 되었거던!!

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x, g, d;
}point;
 
point Q[222 * 222 * 33];
int K, H, W;
int visit[32][222][222];
int map[222][222];
int Q_Front = -1, Q_Back = -1;
int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
int horse[8][2] = { {-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };
 
int main()
{
    memset(map, -1, sizeof(map));
    scanf("%d %d %d", &K, &W, &H);
 
    for (int i = 4; i <= H + 3; i++)
        for (int j = 4; j <= W + 3; j++)
            scanf("%d", &map[i][j]);
 
    Q[++Q_Back].y = 4;
    Q[Q_Back].x = 4;
    Q[Q_Back].d = 0;
    Q[Q_Back].g = 0;
    visit[0][4][4] = 1;
 
    while (Q_Front != Q_Back)
    {
        int y = Q[++Q_Front].y;
        int x = Q[Q_Front].x;
        int g = Q[Q_Front].g;
 
        if (y == H + 3 && x == W + 3)
        {
            printf("%d\n",Q[Q_Front].d);
            return 0;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (map[yy][xx] == -1)
                continue;
 
            if (map[yy][xx] == 0 && visit[g][yy][xx] == 0)
            {
                Q[++Q_Back].y = yy;
                Q[Q_Back].x = xx;
                Q[Q_Back].d = Q[Q_Front].d + 1;
                Q[Q_Back].g = g;
                visit[g][yy][xx] = 1;
            }
        }
 
        for (int a = 0; a < 8; a++)
        {
            int yyy = y + horse[a][0];
            int xxx = x + horse[a][1];
 
            if (map[yyy][xxx] == -1)
                continue;
 
            if (map[yyy][xxx] == 0 && g + 1 <= K && visit[g + 1][yyy][xxx] == 0 )
            {
                Q[++Q_Back].y = yyy;
                Q[Q_Back].x = xxx;
                Q[Q_Back].d = Q[Q_Front].d + 1;
                Q[Q_Back].g = g + 1;
                visit[g + 1][yyy][xxx] = 1;
            }
        }
 
    }
    printf("-1\n");
    return 0;
}