[백준 7562] 나이트의 이동

나이트의 이동

문제설명

테스트 케이스의 수를 입력받고, 체스판의 크기, 시작점과 도착점을 각각 입력받는다.
그리고 시작점에서 도착점까지 나이트가 이동할 때 최소의 이동 수를 구하여라.
이동 가능한 칸은 사진의 그림과 같다.

알고리즘

1. 테스트 케이스의 수를 입력받고, 필요한 입력을 받는다.
2. bfs함수를 실행한다.
3. 시작점을 queue에 넣고 방문여부를 체크한다.
4. queue가 비기전까지 반복하는데, x,y좌표를 꺼낸다.
5. x,y가 도착점과 일치하면 graph의 해당 좌표 값을 출력한다.
6. 나이트가 이동가능한 경우 8개를 각각 배열에서 read해서 체스판의 범위 확인 후 가능하면 방문한다.
7. 4-6의 과정을 반복하여 방문하고 graph를 갱신해서 값을 출력한다.

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <queue>
using namespace std;
#define MAX 301
int graph[MAX][MAX];
bool visited[MAX][MAX];
int I, a, b, c, d;
int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };


void BFS(int x, int y)
{
    queue <pair<int, int>> q;
    q.push({x,y});//시작점 넣기 
    visited[x][y] = true;

    while (!q.empty())
    {
        int x = q.front().first;//queue의 앞의 값 불러오기 
        int y = q.front().second;

        if (x == c && y == d)//도착점에 도달하면 값 출력 후 중단 
        {
            cout << graph[c][d] << "\n";
            return;
        }

        q.pop();//읽은 값 빼기

        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];//이동할 좌표
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= I || ny >= I)//체스판의 크기를 넘으면 스킵
                continue;
            if(!visited[nx][ny])//방문 한 적 없으면 방문 
            {
                graph[nx][ny] = graph[x][y] + 1;//위치= 이동수 갱신 
                q.push({ nx,ny });
                visited[nx][ny] = true;//방문 
            }
        }
    }

}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;

    while (T)
    {
        //판 크기, 시작점과 도착점 입력 받기
        cin >> I >> a >> b >> c>>d;
        //값 초기화
        fill(&graph[0][0],&graph[I][I],0);//전부 이동 할 수 있으므로 1로 초기화
        fill(&visited[0][0], &visited[I][I], 0);
        BFS(a, b);    
        T--;
    }


    return 0;
}

고찰

bfs알고리즘을 활용하여 풀 수 있는 문제였다.