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

1600번: 말이 되고픈 원숭이

BFS

---

1. 문제 해결 아이디어

이동할 수 있는 방향이 동서남북 외에도 체스의 말(house)이 움직일 수 있는 8방향이 추가된 문제이다.

 

처음엔 그냥 8방향만 추가해 주고, 말이 움직이는 방향을 먼저 탐색해 주면 풀리겠지 해서 빠르게 틀렸다.

 

 

[백준 14442] 벽 부수고 이동하기2 C++

위 문제에서 적용했던 것처럼 방문 여부를 3차원으로 만들어줘야 한다.

 

무조건 말처럼 이동을 먼저하는게 아니라 일반 이동을 먼저 할 수도 있기 때문이다.

 

1
4 4
0 0 0 0
1 0 0 0
0 0 1 1
0 1 0 0
같은 경우에는 
(0, 0) > (0, 1) >  (1, 1) >  (2, 1) > 말처럼 이동 > (3, 3) 이 답이 되기 때문이다.

---

2. 코드

#include <iostream>
#include <queue>
 
#define pii pair<int, int>
using namespace std;
 
struct P{
    int r, c;
    int k;
    int cnt;
};
 
int K, W, H;
int Map[201][201];
bool visited[201][201][31];
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
int hr[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int hc[8] = {-2, 2, -1, 1, -2, 2, -1, 1};
 
void BFS(){
    int cnt = 0;
    
    queue<P> que;
    que.push({0, 0, 0, 0});
    for(int i = 0; i <= K; i++){
        visited[0][0][i] = true;
    }
    
    while(!que.empty()){
        P now = que.front();
        que.pop();
        
        if(now.r == H-1 && now.c == W-1){
            cout << now.cnt << "\n";
            return;
        }
        
        if(now.k < K){
            for(int i = 0; i < 8; i++){
                int nr = now.r + hr[i];
                int nc = now.c + hc[i];
                
                // 말 처럼 k+1번 이동했을 때 방문하지 않았다면
                if(nr < 0 || nr >= H || nc < 0 || nc >= W || Map[nr][nc] || visited[nr][nc][now.k+1]) continue;
                visited[nr][nc][now.k+1] = true;
                que.push({nr, nc, now.k+1, now.cnt+1});
            }
        }
        
        for(int i = 0; i < 4; i++){
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            
            // 말 처럼 k번 이동했을 때 방문하지 않았다면 
            if(nr < 0 || nr >= H || nc < 0 || nc >= W || Map[nr][nc] || visited[nr][nc][now.k]) continue;
            visited[nr][nc][now.k] = true;
            que.push({nr, nc, now.k, now.cnt+1});
        }
    }
    cout << -1;
}
 
void input(){
    cin >> K >> W >> H;
    
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> Map[i][j];
        }
    }
}
 
int main(){
    input();
    BFS();
    return 0;
}
 

 

맨날 2차원 방문 배열만 쓰니까 다른것도 써보라고 가르쳐준 문제