[BaekJoon/백준] 1600번 말이 되고픈 원숭이

 

오늘 원래 경사로 문제를 풀려고 했는데, 며칠째 붙잡아도 못 풀겠다.

진심 이게 왜 55퍼센트 정답률이지.. 난 돌대가린가.

 

 

어쩔 수 없이 다른 문제를 찾다가 이 문제를 풀게 되었다.

 

 

키포인트는 VISIT을 3차원 배열로 구성한 것이다.

VISIT[z][x][y] : z는 말 움직임으로 움직인 횟수, x와 y는 좌표를 말한다.

이것만 활용하면 문제를 풀 수 있다.

 

 

나머지 코드 작성은 일반적인 bfs문제 코드 유형과 동일하다.

#include <iostream>
#include <queue>

using namespace std;

int MAP[201][201];

int mx1[4] = {0, 0, -1, 1}; // 일반 움직임
int my1[4] = {1, -1, 0, 0}; // 일반 움직임

int mx2[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 말 움직임
int my2[8] = {-2, -1, 1, 2, -2, -1, 1, 2}; // 말 움직임

int VISIT[31][201][201]; // 말움직임횟수, x, y

int N, M, K;

int bfs() {
     
    queue<pair<int, pair<int, int>>> que; // {말움직임 횟수, {x, y}}
    
    que.push({0, {0, 0}});
    VISIT[0][0][0] = 1;
    
    
    while(!que.empty()) {
        
        
        int c = que.front().first;
        
        int x = que.front().second.first;
        int y = que.front().second.second;
        
        que.pop();
        
        if(x == N - 1 && y == M - 1)
            return VISIT[c][x][y] - 1; // VISIT과 DEPTH를, VISIT 하나로 활용하기위해 시작지점을 1로 초기화했기에 마지막에 뺴줌.
        
        for(int i = 0; i < 4; i++) { // 일반 움직임
            
            
            int tx = x + mx1[i];
            int ty = y + my1[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            if(VISIT[c][tx][ty] == 0 && MAP[tx][ty] != 1) {
                
                que.push({c, {tx, ty}});
                VISIT[c][tx][ty] = VISIT[c][x][y] + 1;
                
            }
        }
        
        if(c + 1 <= K) { // 말 움직임 가능하면
            
            for(int i = 0; i < 8; i++) { // 일반 움직임
                
                
                int tx = x + mx2[i];
                int ty = y + my2[i];
                
                if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                    continue;
                
                if(VISIT[c + 1][tx][ty] == 0 && MAP[tx][ty] != 1) {
                    
                    que.push({c + 1, {tx, ty}});
                    VISIT[c + 1][tx][ty] = VISIT[c][x][y] + 1;
                }
            }

            
            
            
        }
        
        
        
    }
    
    return -1;
    
}

int main() {
    
    cin >> K >> M >> N; // 입력 순서 주의!
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            cin >> MAP[i][j];
            
        }
    }
    
    cout << bfs() << "\n";
    
    
    
}

 

 

 

소요 시간 : 35분