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

 

문제를 읽어보고 오자.

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

1600번: 말이 되고픈 원숭이

 

문제를 읽어 보면 그래프 탐색을 사용하는 문제인 것을 알 수 있다. 하지만 약간 까다로운 점은, 특정 조건의 이동을 특정한 횟수 안에 실행한다는 점이다. 이것에 대한 모든 경우를 세야 할까?

 

나는 처음에 말처럼 움직인 횟수를 큐에 저장해서 확인해 보았다. 하지만 이러한 방법을 사용하니 방문한 경우에 대해서 오류가 있다는 것을 알게 되었다. 벽 부수기 문제 ( https://www.acmicpc.net/problem/2206 ) 처럼 한 개의 벽을 부수는 것처럼, 3차원 배열을 이용해야 함을 알게 되었다.

 

3차원 배열을 이용하여 말처럼 이동을 할 때, 다음 차원으로 넘어가야 정상적인 결과를 도출할 수 있다. 말처럼 n번 이동했을 경우에는, n번째 차원에서 생각해야지 서로 방해하지 않게 된다. 기본적인 탐색 방법은 BFS를 이용한다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
/*
dp로 풀이가 될까 했으나, 길이 보이지 않았음.
예전에 비슷한 문제를 풀이한 적이 있어서 참고했다. (백준 2206)
x,y,horse 의 3개 변수값을 가지고 있는 큐를 선언.
3차원 배열을 통해서 K + 1 개의 차원에서 bfs를 돌린다.
각각의 차원에서 알아서 탐색이 될 것이며, 가장 빨리 목표에 도달하는 곳이 정답일 것이다.
정답에 도달하지 못하면 while문을 빠져나와 -1을 반환하게 될 것이다.
*/
 
typedef struct
{
    int x, y, horse;
} loc;
 
int map[200][200];
int visited[200][200][30];
int K, W, H;
 
int bfs()
{
    queue<loc> q;
    int move_horse_x[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int move_horse_y[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int move_x[4] = {1, -1, 0, 0};
    int move_y[4] = {0, 0, 1, -1};
    int ans = -1;
 
    visited[0][0][0] = 1;
    q.push((loc){0, 0, 0});
    while (!q.empty())
    {
        loc a = q.front();
        q.pop();
        int x = a.x;
        int y = a.y;
        int horse = a.horse;
        if ((y == H - 1) && (x == W - 1))
            return (visited[y][x][horse] - 1);
        /* 일반적인 인접한 곳 이동 */
        for (int i = 0; i < 4; i++)
        {
            int dx = x + move_x[i];
            int dy = y + move_y[i];
            if (dx >= 0 && dx < W && dy >= 0 && dy < H && !map[dy][dx] && !visited[dy][dx][horse])
            {
                visited[dy][dx][horse] = visited[y][x][horse] + 1;
                q.push((loc){dx, dy, horse});
            }
        }
        /* 말처럼 이동 */
        for (int i = 0; i < 8; i++)
        {
            int dx = x + move_horse_x[i];
            int dy = y + move_horse_y[i];
            if (dx >= 0 && dx < W && dy >= 0 && dy < H && !map[dy][dx] && !visited[dy][dx][horse + 1] && horse < K)
            {
                visited[dy][dx][horse + 1] = visited[y][x][horse] + 1;
                q.push((loc){dx, dy, horse + 1});
            }
        }
    }
    return (-1);
}
 
int main()
{
    //freopen("test", "r", stdin);
    cin >> K >> W >> H;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            cin >> map[i][j];
 
    cout << bfs();
    return (0);
}

 

알고리즘의 세계는 끝이 없다. ㅠㅜ 나중에 한번 체계적으로 공부를 해봐야 할 것 같다.