[백준] 16948번 - 데스 나이트 / C++

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

 

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

 

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

 

코드

#include <iostream>
#include <queue>

using namespace std;

int N;
int night[2][2];
bool visited[201][201];
int dr[] = {-2, -2, 0, 0, 2, 2};
int dc[] = {-1, 1, -2, 2, -1, 1};

int bfs()
{
	queue< pair<int, int> > q;
	int i, j, size, res = 0;
	int r, c, nr, nc;

	visited[night[0][0]][night[0][1]] = true;
	q.push(make_pair(night[0][0], night[0][1]));
	while (!q.empty())
	{
		res++;
		size = q.size();
		for (i = 0; i < size; i++)
		{
			r = q.front().first;
			c = q.front().second;
			q.pop();
			for (j = 0; j < 6; j++)
			{
				nr = r + dr[j];
				nc = c + dc[j];
				if (nr == night[1][0] && nc == night[1][1])
				{
					return res;
				}
				if (nr > 0 && nr <= N && nc > 0 && nc <= N)
				{
					if (!visited[nr][nc])
					{
						visited[nr][nc] = true;
						q.push(make_pair(nr, nc));
					}
				}
			}
		}
	}
	return -1;
}

int main()
{
	cin >> N;
	cin >> night[0][0] >> night[0][1];
	cin >> night[1][0] >> night[1][1];
	cout << bfs() << endl;
	return 0;
}

 

출발지부터 너비 우선 탐색을 수행하여 목적지에 이르기까지 몇 번의 이동이 필요한지 계산한다.

이동가능한 모든 경로에 대하여 이동 후 위치가 방문되지 않은 곳이라면 큐에 삽입한다.

목적지에 도착하면 누적된 이동 횟수를 리턴하고, 탐색이 끝날 때까지 목적지에 이르지 못하면 -1을 리턴한다.

 

링크

16948번: 데스 나이트

inbdni/Baekjoon