[C++/백준] 1600번: 말이 되고픈 원숭이

문제 링크

1600번: 말이 되고픈 원숭이

 

풀이

BFS로 푸는 문제. 처음에 메모리 초과가 났는데, 말로 오는 경우와 그냥 오는 경우 방문 처리를 같게 해서 그랬음

1. 먼저 원숭이가 갈 수 있는 위치를 정해주기 위한 dy와 dx를 지정한다.
2. 입력을 받으며 dist도 INF로 초기화해준다. dist 배열은 3차원 배열인데, 말로 이동한 횟수의 각 위치 거리를 계산하기 위함이다.
3. BFS를 통해 탐색한다. q는 tuple로 각 위치와 말로 이동한 횟수를 넣어준다.
   1. 원숭이가 이동할 수 있는 자리는 12개인데, 말로 이동한 횟수가 k를 넘어서면 말로 이동을 못하기 때문에 continue
   2. 해당 위치가 범위를 넘어서거나, 갈 수 없는 위치라면 continue
   3. 말로 오는 경우 dist[ny][nx][cnt+1]이 왔던 위치인지 확인하고, 아니라면 dist[ny][nx][cnt]를 확인한다.
   4. dist를 갱신하고 q에 넣어주어 q가 빌 때까지 반복한다.
4. 이렇게 하면 각 말로 이동 횟수에 해당 위치까지 거리가 나올텐데, 이 중 최솟값을 출력한다.

 

코드

#include <iostream>
#include <queue>
#include <tuple>
#define INF 40001
using namespace std;

int arr[201][201];
int dist[201][201][32]; // k번 말로 이동하는 수를 체크하기 위함

int k, w, h;

int dy[12] = { -1,0,1,0 ,-1,-2,-2,-1,1,2,2,1 }; // 그냥 오는거, 말로 오는거
int dx[12] = { 0,1,0,-1,-2,-1,1,2,-2,-1,1,2 };

void BFS()
{
    queue<tuple<int, int, int>> q;
    dist[0][0][0] = 0;
    q.push(make_tuple(0, 0, 0));

    while (!q.empty())
    {
        int ty, tx, cnt;
        tie(ty, tx, cnt) = q.front();
        q.pop();
        for (int i = 0; i < 12; i++)
        {
            if (cnt >= k && i >= 4) continue; // 말로 이동 횟수를 넘어서서는 이동을 못하게
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            if (arr[ny][nx] == 1) continue;
            if (i >= 4) // 말로 오는 경우
            {
                if (dist[ny][nx][cnt + 1] != INF) continue;
                dist[ny][nx][cnt + 1] = dist[ty][tx][cnt] + 1;
                q.push(make_tuple(ny, nx, cnt + 1));
            } 
            else
            {
                if (dist[ny][nx][cnt] != INF) continue;
                dist[ny][nx][cnt] = dist[ty][tx][cnt] + 1;
                q.push(make_tuple(ny, nx, cnt));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k >> w >> h;

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> arr[i][j];
            for (int l = 0; l <= k; l++)
            {
                dist[i][j][l] = INF;
            }
        }
    }

    BFS();

    int ans = INF;
    for (int i = 0; i <= k; i++)
    {
        ans = min(ans, dist[h - 1][w - 1][i]);
    }
    if (ans == INF) cout << -1;
    else cout << ans;
}