[BaekJoon/백준] 7562번 나이트의 이동

 

 

BFS 유형의 문제이다.

 

2차원 배열로 시작해서 풀었는데

1차원 + 숫자 연산만으로 좀 더 간단하게 풀 수 도 있다. (ex. 1697번 : https://hevton.tistory.com/422 )

// 생각해보니, 굳이 2차원 배열을 다루지 않고 그냥 숫자로만 해도 구현할 수 있을 것 같다.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int T, N;

bool VISIT[300][300];
int DEPTH[300][300];

int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int my[8] = {-2, -1, 1, 2, -2, -1, 1, 2};

int START_X, START_Y, FIN_X, FIN_Y;

// x y 좌표 두개를 그냥 이용해서 구현해도 되고, 하나의 숫자로 나타낸 뒤에 / % 해줘서 구현해도 되고.
void bfs(int x, int y) {
    
    queue<pair<int,int>> que;
    
    que.push({x, y});
    VISIT[x][y] = true;
    
    
    while(!que.empty()) {
        
        int xx = que.front().first;
        int yy = que.front().second;
        
        int tx, ty;
        
        que.pop();
        
        for(int i = 0; i < 8; i++) {
            
            tx = xx + mx[i];
            ty = yy + my[i];
            
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= N) // 벗어났다면
                continue;
            
            if(VISIT[tx][ty]) // 이미 간 곳이라면
                continue;
            
            
            DEPTH[tx][ty] = DEPTH[xx][yy] + 1;
            que.push({tx, ty});
            VISIT[tx][ty] = true;

            
            if(tx == FIN_X && ty == FIN_Y) {
                return;
            }
                
            
        }
        
        
    }
    
    
}

int main() {
        
    cin >> T;
    
    
    while(T--) {
        
        cin >> N;
                    
        cin >> START_X >> START_Y;
                        
        cin >> FIN_X >> FIN_Y;
                                

        memset(VISIT, 0, sizeof(VISIT));
        memset(DEPTH, 0, sizeof(DEPTH));
        
        bfs(START_X, START_Y);
        
        
        cout << DEPTH[FIN_X][FIN_Y] << "\n";
        
        
    }
    
}