백준 7562번: 나이트의 이동 (그래프 탐색, 순회)

 

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

 

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

 

 

 

 

------------------------------------------------------------------------------------------

1. 문제 해석

BFS를 이용한 최단 경로 문제이다. 

2차원 배열에서 한 노드로부터 다른 모든 노드까지의 최단 경로를 구하는 알고리즘을 수행한 후,

원하는 도착 지점의 최단경로 값을 출력하면 되는 쉬운 문제이다. 

 

2. 코드 구현

특별하게 이번에는 dir 배열을 이용해서 나이트의 모든 위치 이동을 배열에 담아두었다. 

이렇게 하면 x + dir[i][0] 이 다음 x 좌표, y + dir[i][1] 이 다음 y 좌표가 된다. 

그리고 Cango 함수를 통해서 갈 수 있는 배열 위치인지 확인하는 함수를 따로 만들었다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#define TRUE 1
#define FALSE 0

using namespace std;
int l,T;
int N_x,N_y,D_x, D_y;//now and Destination
int board[301][301];
int visited[301][301];
int dir[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
queue <pair<int, int> > Q;

int dis[301][301];

void init()
{
    for(int i=0;i<l;i++)
    {
        for(int j=0;j<l;j++)
        {
            board[i][j] = 0;
            dis[i][j] = -1;
            visited[i][j] = FALSE;
        }
    }
}
int Cango(int r, int c)
{
    if(r >= 0 && r < l && c >= 0 && c <l)
        return TRUE;
    return FALSE;

}
void find()
{
    Q.push(make_pair(N_y, N_x));
    dis[N_y][N_x] = 0;
    while(!Q.empty())
    {
        int r = Q.front().first;
        int c = Q.front().second;
        Q.pop();
        if(visited[r][c] == TRUE)
            continue;
        visited[r][c] = TRUE;
        for(int i=0;i<8;i++)
        {
            int next_r= r + dir[i][0];
            int next_c = c+ dir[i][1];
            if(Cango(next_r, next_c) && (dis[next_r][next_c] == -1 || dis[next_r][next_c] > dis[r][c] + 1))
            {
                dis[next_r][next_c]  = dis[r][c] + 1;
                Q.push(make_pair(next_r, next_c));
            }
        }

    }

}

int main()
{
    scanf("%d", &T);
    for(int i=0;i<T;i++) {
        scanf("%d", &l);
        init();
        scanf("%d %d", &N_y, &N_x);
        scanf("%d %d", &D_y, &D_x);
        find();
//    printf("distance 확인용 \n");
//        for(int i=0;i<l;i++)
//        {
//
//            for(int j=0;j<l;j++)
//            {
//               printf("%d ", dis[i][j]);
//            }
//            printf("\n");
//        }
    printf("%d\n", dis[D_y][D_x]);
    }
}

 

 

주석 처리된 명령문 수행 시 출력되는 distance 배열

(입력이 

 1 (test case 1)

 1 (l size 1) 

1 1 (출발지점)

1 1 (도착 지점)

일 때 경우이다.)

이때의 정답 0