[BFS/DFS] C11 백준 1600 말이 되고픈 원숭이 풀이

문제

• 1600

풀이 과정

• 문제는 나이트의 이동과 비슷한데, 결국 k만큼 말(나이트)처럼 이동할 수 있고 k가 넘어서면 일반이동만 할 수 있다는 조건이 추가 됨
• 어렵진 않은 문제 인 듯, 조건 2개로 이동시키면 됨
  • 시작지점(0,0)->도착지점(h-1,w-1)까지
  • 주의 할 점은 return 값? 정도?
• bfs 사용, 자료구조는 큐

#include <stdio.h>

#define MAX 201
#define H_MAX 31

typedef struct Que {
    int x;
    int y;
    int hk;
} Q;

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

int k,w,h;
int map[MAX][MAX];
int visit[MAX][MAX][H_MAX];

Q que[MAX*MAX*H_MAX];
int front;
int rear;

void enqueue(int x, int y, int hk) {
    que[rear].x = x;
    que[rear].y = y;
    que[rear].hk = hk;
    rear++;
}

Q dequeue() {
    return que[front++];
}

int bfs() {
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.x == h-1 && cur.y == w-1) {
            return visit[cur.x][cur.y][cur.hk];
        }
        
        if (cur.hk < k) {
            for (int i=0; i<8; i++) {
                int nx = cur.x + hx[i];
                int ny = cur.y + hy[i];
            
                if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                    visit[nx][ny][cur.hk+1] == 0 && map[nx][ny] == 0) {
                    visit[nx][ny][cur.hk+1] = visit[cur.x][cur.y][cur.hk] + 1;
                    enqueue(nx, ny, cur.hk + 1);
                }
            }
        }
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                visit[nx][ny][cur.hk] == 0 && map[nx][ny] == 0) {
                visit[nx][ny][cur.hk] = visit[cur.x][cur.y][cur.hk] + 1;
                enqueue(nx, ny, cur.hk);
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d", &k);
    scanf("%d %d", &w, &h);
    
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    
    visit[0][0][0] = 0;
    enqueue(0, 0, 0);
    int result = bfs();
    printf("%d", result);
    
    return 0;
}