백준온라인저지(BOJ)/#7562/나이트의이동/BFS

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

7562번: 나이트의 이동

 

기존의 2차원 좌표에서 BFS, DFS를 할 때 상하좌우 좌표에서 확장하여 생각할 수 있다. 

위의 그림과 같이 체스 위의 나이트는 총 8가지 경우의 수로 좌표 이동이 가능하다.

이 점을 염두에 두고, const dy[], const dx[] 좌표를 8개 고정으로 박아둔 뒤, 순회해주면서 탐색하면 된다. 

+

//cost[][]를 도입하여, 시작지점 i, j의 cost[i][j] = 0으로 하고, 다른 좌표의 cost를 인접우선탐색하면서

// +1 씩 해준다. 이때 우리가 이동하고자 하는 좌표 (k,l)의 cost[k][l] 에 마킹되는 값이 답이 된다

 

[구현코드]

---

#include <vector>
#include <queue>
#include <iostream>

using namespace std;
vector<vector<int>> cost;
int y1,y2,x1,x2;
const int dy[] = {1,2,2,1,-1,-2,-2,-1};
const int dx[] = {-2,-1,1,2,2,1,-1,-2};

int I; // M은 가로, N은 세로를 의미

void bfs( int y1, int x1, int y2, int x2){
    queue<pair<int, int>> q;
    q.push(make_pair(y1,x1));
    
    while(!q.empty()){
        pair<int,int> here = q.front();
        
        if(y1 == y2 && x1 == x2){
            break;
        }
        q.pop();
        
        for(int m = 0; m < 8; m++){
            int next_y = here.first + dy[m];
            int next_x = here.second + dx[m];
            if(next_y >= 0 && next_y < I
               && next_x >= 0 && next_x < I
               && cost[next_y][next_x] == 0){
                cost[next_y][next_x] = 1 + cost[here.first][here.second];
                q.push(make_pair(next_y,next_x));
            }
        }
    }
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>I;
        cost.clear();
        cost.resize(I,vector<int>(I,0));
        cin>>y1>>x1;
        cin>>y2>>x2;
        bfs(y1, x1, y2, x2);
        cout<<cost[y2][x2]<<'\n';
    }
    return 0;
}