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

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

1600번: 말이 되고픈 원숭이

---

1. Logic

처음에 문제를 무조건 k번 말처럼 이동한 후 기회를 다 쓰고 4방향으로 이동하는 줄 알고 냅다 2차원 방문배열을 만들어서 BFS돌렸더니 당연히 틀렸다. 문제의 의도는 목적지에 도달하기 전까지 k번 이하로 능력을 사용하여 도착하는것이기 때문에 4방향으로 먼저 돌고 능력을 사용해도 된다. 즉 처음위치에서 능력을 쓰고 x칸으로 이동한 것과 능력을 안쓴상태로 x칸으로 이동한 횟수를 다르게 쳐줘야 한다. 비슷한 문제로는 "벽 부수고 이동하기" 시리즈가 비슷할 것 같다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int k, w, h;
int graph[201][201];
bool vis[201][201][31];

int horseMove[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
int generalMove[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

bool check(int y, int x, int hCnt) {
    if(x < 0 || x >= w || y < 0 || y >= h) return false;
    if(vis[y][x][hCnt]) return false;
    if(graph[y][x] == 1) return false;
    return true;
}

int bfs() {
    queue<pair<pair<int, int>, pair<int, int>>> q;
    
    q.push({{0, 0}, {0, 0}});
    vis[0][0][0] = true;
    
    for(int i = 0; i < k; i++) {
        vis[0][0][i] = true;
    }
    
    while(!q.empty()) {
        int cnt = q.front().first.first;
        int hCnt = q.front().first.second;
        int y = q.front().second.first;
        int x = q.front().second.second;
        
        q.pop();
        
        if(x == w-1 && y == h-1) return cnt;
        
        if(hCnt < k) {
            for(int i = 0; i < 8; i++) {
                int nx = x + horseMove[i][0];
                int ny = y + horseMove[i][1];
                
                if(!check(ny, nx, hCnt+1)) continue;
                
                q.push({{cnt+1, hCnt+1}, {ny, nx}});
                vis[ny][nx][hCnt+1] = true;
            }
        }
        
        for(int i = 0; i < 4; i++) {
            int nx = x + generalMove[i][0];
            int ny = y + generalMove[i][1];
            
            if(!check(ny, nx, hCnt)) continue;
            
            q.push({{cnt+1, hCnt}, {ny, nx}});
            vis[ny][nx][hCnt] = true;
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> k >> w >> h;
    
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin >> graph[i][j];
        }
    }
    
    cout << bfs();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐