[백준 / BOJ] 1600 :: 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

문제 설명:

- 시작 지점(제일 왼쪽, 제일 위 (H,1))에서 도착지점 (제일 오른쪽, 제일 아래(1,W))까지 이동하는 최단 거리를 찾자

- 이동할 수 있는 방법에는 두가지가 있다.

 1. 체스판의 나이트 처럼 이동하는 경우(현 자리에서 8가지)

 2. 인접한 칸으로 이동하는 경우(현 자리에서 4가지)

- 이 때 1번의 방법으로 이동하는 경우는 최대 K번까지 사용 가능하다.

 

풀이 / 구현 방법 : 

- BFS

- BFS로 최단 거리를 업데이트 해 나갈 것인데, 이 때 dist[x][y][k] 배열을 사용한다. 이 배열은 x,y까지 1번 이동을 k번 사용하여 이동했을 때의 최단 거리이다.

- BFS로 구현할 때 queue에 넣어두고 꺼내면서 다음에 이동할 수 있는 곳을 탐색하는 로직은 동일하다. 이 이동가능한 로직을 찾는 과정에서 1번과 2번 이동할 수 있는 방법을 모두 구현하면 된다.

- 그리고 K번까지만 사용 가능하므로 현재 K번 사용 횟수 + 1 이 K를 넘으면 이 경우는 이동 불가능한 경우이다.

- 자세한 구현 내용은 소스로!

 

소스코드

#include <iostream>
#include <queue>
#define MAX 987654321
using namespace std;
 
int dx[8] = { -2,-1,1,2,-2,-1,1,2 };
int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
//말이 갈 수 있는 8가지 위치
int adj_x[4] = { -1,1,0,0 };
int adj_y[4] = { 0,0,-1,1 };
//인접해서 갈 수 있는 네 곳
 
int K, W, H;
int map[201][201];
int dist[201][201][31];//dist[x][y][k] : x,y에 k번의 이동으로 도착할 수 있는 최소 횟수
int main() {
    cin >> K >> W >> H;
    for (int i = H; i >=1 ; i--) {
        for (int j = 1; j <= W; j++) {
            cin >> map[i][j];
        }
    } 
    //입력값이 H가 큰 순서로 들어옴을 유의(위에서 아래로 입력이 들어옴)
 
    for (int i = 0; i < 201; i++) {
        for (int j = 0; j < 201; j++) {
            for (int k = 0; k < 31; k++) {
                dist[i][j][k] = MAX;
            }
        }
    }
    //dist 값 초기화
 
    queue<pair<pair<int, int>,int> > q;
    dist[H][1][0] = 0;//시작 지점 왼쪽 위
    q.push({ { H,1 },0 });
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
 
        //말이 이동하듯이 이동
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (nx <1 || nx > H || ny < 1 || ny > W || map[nx][ny] == 1) continue;//이동 불가능한 곳
            if (dist[nx][ny][cnt + 1] > dist[x][y][cnt] + 1 && cnt + 1 <= K) { //나이트처럼 이동한 횟수가 K를 넘으면 이동 불가
                dist[nx][ny][cnt + 1] = dist[x][y][cnt] + 1;
                q.push({ {nx,ny},cnt + 1 });
            }
        }
 
        //인접한 곳 이동
        for (int k = 0; k < 4; k++) {
            int nx = x + adj_x[k];
            int ny = y + adj_y[k];
            if (nx <1 || nx > H || ny < 1 || ny > W || map[nx][ny] == 1) continue;//이동 불가능한 곳
            if (dist[nx][ny][cnt] > dist[x][y][cnt] + 1) {
                dist[nx][ny][cnt] = dist[x][y][cnt] + 1;
                q.push({ {nx,ny},cnt});
            }
        }
 
    }
    int ans = MAX;
    for (int i = 0; i <= K; i++) {
        if (ans > dist[1][W][i]) ans = dist[1][W][i];
    }
    if (ans == MAX) cout << "-1" << '\n';
    else cout << ans << endl;
}