백준 1600번 말이 되고픈 원숭이 - C++ 풀이

---

 

1. 원숭이의 위치 {r, c}와 말처럼 이동한 횟수 k로 원숭이의 상태를 나타낼 수 있다.
2. 원숭이의 상태를 그래프의 노드로 생각하고, 한 번의 이동으로 도달 가능한 상태를 모두 간선으로 잇는다.
3. 출발 상태 노드에서 도착 상태 노드로 가는 최단 거리를 BFS를 사용하여 구한다.

 

1. 원숭이의 위치 {r, c}와 말처럼 이동한 횟수 k로 원숭이의 상태를 나타낼 수 있다.

 원숭이의 상태를 나타내기 위해서 필요한 값은, 원숭이의 위치와 현재 위치까지 오면서 말(knight)처럼 이동한 횟수 k이다.

 

2. 원숭이의 상태를 그래프의 노드로 생각하고, 한 번의 이동으로 도달 가능한 상태를 모두 간선으로 잇는다.

 원숭이의 {r, c, k} 값을 가지고 원숭이 상태 노드를 나타낸다. 그리고 한 번의 이동으로 도달 가능한 상태들끼리 간선으로 이어준다.

 

3. 출발 상태 노드에서 도착 상태 노드로 가는 최단 거리를 BFS를 사용하여 구한다.

 그래프에서 하나의 간선은 한 번의 이동을 의미하므로, 출발 상태 노드 {0, 0, 0}에서 도착 상태 노드 {H-1, W-1, k(<=K)}로 가는 최단 거리가 곧 최소 이동 횟수가 된다. BFS를 이용해서 노드와 노드 사이 거리를 구할 수 있다.

반응형

---

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

struct Node {
    int r, c, k;  
};

int K, W, H;
int board[200][200];
bool visit[200][200][31];

int dr[] = {-1, 1, 0, 0, -2, -2, -1, -1, 1, 1, 2, 2};
int dc[] = {0, 0, -1, 1, -1, 1, -2, 2, -2, 2, -1, 1};

int BFS(pii s, pii e) {
    queue<pair<int, Node>> q;
    
    q.push({0, {s.first, s.second, 0}});
    visit[s.first][s.second][0] = true;
    
    while (!q.empty()) {
        int dist = q.front().first;
        Node node = q.front().second;
        q.pop();
        
        if (node.r == e.first && node.c == e.second) return dist;
        
        for (int i=0; i<(node.k < K ? 12 : 4); i++) {
            int nr = node.r + dr[i];
            int nc = node.c + dc[i];
            int nk = i >= 4 ? node.k+1 : node.k;
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (visit[nr][nc][nk] || board[nr][nc] == 1) continue;
            
            q.push({dist+1, {nr, nc, nk}});
            visit[nr][nc][nk] = true;
        }
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> K >> W >> H;
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            cin >> board[i][j];
        }
    }
    
    cout << BFS({0, 0}, {H-1, W-1});

    return 0;
}