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

정석적인 너비 우선 탐색 (BFS) 가 아닌 약간은 변형된 형태의 문제이다. 이런 류의 문제가 코딩 테스트에서 꽤 자주 나오는거 같던데 좀 더 익숙해질 필요가 있다고 생각한다.

문제 설명부터 하자면은, 원숭이 한마리가 체스에 있는 말 처럼 K번 움직일 수 있는 조건 하에 오른쪽 아래에 도착 지점까지 갈 수 있는 최소 경로를 구하면 된다.

먼저 예전같이 작은 실수로 망하지 않게 Dir 방향을 제대로 지정해주었고 체스 말 움직임 좌표도 잘 지정해주었다. 다만, 이 문제에 핵심은 최소 경로를 구하기 위해서 모든 경우의 수를 넣어줘야 했던것이다.

예를 들어 체스 움직임으로 이동한 좌표와 그냥 움직여서 이동한 좌표가 겹칠 수가 있고 서로 다른 경로로 표시를 해주어야 했던것이다. 벽 부수고 이동하기와 같은 원리로 이 문제는 일반적인 visited 를 사용하는게 아닌 3차원 벡터를 사용했어야했다.

경로를 특정 조건에 맞춰서 다른 경로로 인식 시켜야 할때 사용하는 방법인데 참 새롭고 유용한 방법같다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int K, N, M; 
int matrix[201][201]; 
bool visited[201][201][31]; 

vector<pair<int,int>> horseDir = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
vector<pair<int,int>> Dir = {{0,1},{0,-1},{1,0},{-1,0}}; 

struct Monkey{
    int x,y,move,distance; 
};

void Input(){
    cin >> K >> M >> N;
    for(int i  = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> matrix[i][j]; 
        }
    }
}

void Solution(){
    memset(visited,false,sizeof(visited)); 
    int answer = -1; 
    queue<Monkey> q;
    q.push({0,0,K,0}); 
    visited[0][0][0] = true;
    while(!q.empty()){
        int size = q.size(); 
        for(int i = 0; i < size; i++){
            Monkey first = q.front();
            q.pop(); 

            int x = first.x, y = first.y, dist = first.distance, horseMove = first.move;

            if(x == N-1 && y == M-1){
                cout << dist; 
                return; 
            }

            if(horseMove > 0){
                for(pair<int,int>& p : horseDir){
                    int nX = x + p.first;
                    int nY = y + p.second;

                    if(nX < 0 || nY < 0 || nX >= N || nY >= M || matrix[nX][nY] == 1 || visited[nX][nY][horseMove-1]) continue; 

                    visited[nX][nY][horseMove-1] = true; 
                    q.push({nX,nY,horseMove-1,dist+1}); 
                }
                
            }
            
            
            for(pair<int,int>& p : Dir){
                int nX = x + p.first;
                int nY = y + p.second;

                if(nX < 0 || nY < 0 || nX >= N || nY >= M || matrix[nX][nY] == 1 || visited[nX][nY][horseMove]) continue; 

                visited[nX][nY][horseMove] = true; 
                q.push({nX,nY,horseMove,dist+1});
            }
            
            
        }
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. BFS 활용
2. 시뮬레이션 이해