[BOJ] 말이 되고픈 원숭이_1600 C++ 풀이

문제

원숭이는 상하좌우로 이동 가능하며 k번의 능력을 사용하여 체스의 나이트와 같은 8가지 방향으로 이동할 수 있다고 할 때, 격자판의 맨 왼쪽 상단에서 맨 오른쪽 하단 까지 이동하는데 걸리는 최소 이동회수를 출력 하는 문제이다.

접근 방법

여느 그래프 탐색 문제와 마찬가지로 구조체로 원숭이의 상하좌우 이동과, 나이트의 이동을 구현한 후에 너비 우선 탐색을 사용하여 격자판 배열의 마지막 인덱스 위치까지 도달 하는데 걸리는 이동 회수를 출력하면 될것이라 생각 하였지만 간과 했던 문제가 있었다.

바로 같은 정점이어도 능력을 사용하고 방문 했는가 아닌가에 따라 해당 정점 까지의 최소 방문 횟수가 달라질 수가 있다. 따라서 방문한 정점을 기록하는 visited 배열을 2차원이 아닌 3차원으로 선언하여 visited[x][y][a] x,y 지점에 능력을 a 번 사용해서 왔습니다. 로 표현 해야 했다.

매번 그래프 문제를 풀 때 마다 실수 하는 건데 배열의 인덱스값으로 row, col 혹은 x,y를 사용하여 정점을 이동 방문 할 때는 유의 해야 한다. 예를 들어 아래의 map[nextX][nextY]의 경우 nextX는 map의 새로$($h)의 경계를 신경 써야하고 nextY는 map의 가로$($w)의 경계를 주의 해야 한다.

구현

#include<iostream>
#include<queue>
using namespace std;

typedef struct
{
    int x,y;
} D;

D dir[4]={ {0, -1}, {1, 0}, {-1, 0}, {0, 1} };
D horse[8]={ {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {1, 2}, {2, 1}, {-1, 2}, {-2, 1} };
int map[200][200];
int visited[200][200][31];
int k, w, h; // w = 가로, h = 세로

int bfs(void)
{
    queue<pair<pair<int, int>, pair<int, int> > >q;

    q.push(make_pair(make_pair(0, 0), make_pair(0, 0))); // x좌표, y좌표, 이동거리횟수, 능력사용횟수
    visited[0][0][0]=1;
    while(!q.empty())
    {
        int X = q.front().first.first;
        int Y = q.front().first.second;
        int cnt = q.front().second.first;
        int ability = q.front().second.second;
        if(X == h-1 && Y == w-1) return cnt; // X와 h, Y와 w 비교하는 것 주의
        q.pop();
        
        if(ability<k) // 말이 될수 있는 회수가 남아 있을 경우
        {
            for(int i=0; i<8; i++)
            {
                int nextX = X + horse[i].x;
                int nextY = Y + horse[i].y;
                if(0<=nextX && nextX<h && 0<=nextY && nextY<w)
                    if(!visited[nextX][nextY][ability+1] && !map[nextX][nextY]) // 이동하는 칸이 방문한 적이 없고 장애물이 없으면
                    {
                        q.push(make_pair(make_pair(nextX,nextY), make_pair(cnt+1, ability+1)));
                        visited[nextX][nextY][ability+1]=1;
                    }
            }
        }
        
        for(int i=0; i<4; i++)
        {
            int nextX = X + dir[i].x;
            int nextY = Y + dir[i].y;
            if(0<=nextX && nextX<h && 0<=nextY && nextY<w)
                if(!visited[nextX][nextY][ability] && !map[nextX][nextY]) // 이동하는 칸이 방문한 적이 없고 장애물이 없으면
                {
                    q.push(make_pair(make_pair(nextX,nextY), make_pair(cnt+1, ability)));
                    visited[nextX][nextY][ability]=1;
                }
        }
        
    }
    return -1;
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>k;
    cin>>w>>h;

    for(int i=0; i<h; i++)
        for(int j=0; j<w; j++)
            cin>>map[i][j];
        
    cout<<bfs();
    return 0;
}

BOJ_말이 되고픈 원숭이