[백준OJ] 7562번 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

---

 

풀이)

BFS로 풀 수 있다. BFS의 기본 상하좌우에서 말의 이동방향으로 배열을 선언해둔뒤, 일반적인 BFS를 수행시켜주면된다.

 

시간복잡도)

인접행렬BFS를 수행했으므로, O(l*l)이 된다.

 

코드)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define MAX 987654321
using namespace std;

int mv[8][2]={{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1},{-2,1},{-2,-1}};
int n;
bool visited[300][300];
int maze[300][300];
bool isIn(int i,int j){
    return i>=0&&i<n&&j>=0&&j<n;
}

void bfs(pair<int,int> st, pair<int,int> end){
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            maze[i][j]=MAX;
        }
    }

    
    q.push({st.first,st.second});
    visited[st.first][st.second]=true;
    maze[st.first][st.second]=0;
    while(!q.empty()){
        int nowi=q.front().first;
        int nowj=q.front().second;
        
        q.pop();
        if(nowi==end.first&&nowj==end.second){
            cout<<maze[nowi][nowj]<<"\n";
            return;
        }
        
        for(int i=0;i<8;i++){
            int ni=nowi+mv[i][0];
            int nj=nowj+mv[i][1];
            
            
            if(isIn(ni,nj)&&!visited[ni][nj]){
                q.push({ni,nj});
                visited[ni][nj]=true;
                maze[ni][nj]=min(maze[ni][nj],maze[nowi][nowj]+1);
            }
        }
    }
    return;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        pair<int,int> st,end;
        cin>>st.first>>st.second>>end.first>>end.second;
        memset(visited,false,sizeof(visited));
        bfs(st,end);
    }
}