백준 : : 7562번 나이트의 이동- C++ 풀이

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

7562번: 나이트의 이동

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {1, -1, 2, -2, 2, -2, 1, -1};
 
 
int graph[301][301];
bool visited[301][301];
 
int bfs(int size, int beginX, int beginY, int endX, int endY){
    queue<pair<int, int> > q;
 
    q.push(make_pair(beginX, beginY));
    visited[beginX][beginY] = true;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
 
        q.pop();
 
        if(x == endX && y == endY) return graph[x][y];
 
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];//이동하기 
            int ny = y + dy[i];
            if(nx < 0 || nx >= size || ny < 0 || ny >= size) continue;
            if(visited[nx][ny] == true) continue;
            else{
                visited[nx][ny] = true;
                q.push(make_pair(nx, ny));
                graph[nx][ny] = graph[x][y] + 1;
            }       
        }
    }
    return graph[endX][endY];
}
 
 
int main(void){
    int n, m;
    int beginX, beginY;
    int endX, endY;
 
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> m;
        memset(visited, 0, sizeof(visited));
        memset(graph, 0, sizeof(graph));
        cin >> beginX >> beginY >> endX >> endY;
        cout << bfs(m, beginX, beginY, endX, endY) << endl;
    }
}

 

최단 거리 : BFS
문제 많이 풀어보자