C++ / 16948 / 데스 나이트 ( 너비 우선 탐색 )

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

문제 요약

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었습니다.

데스 나이트가 있는 곳이 (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번부터 시작합니다.

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

		O
O				O
		데스 나이트
O				O
		O

문제 풀이

1. 체스판 크기를 입력받고 나이트의 위치와 목표 위치를 입력받습니다.

2. 체스판을 -1로 채웁니다. ( 도달하지 못하는 위치를 -1로 출력하게 하기 위함 )

3. bfs 탐색을 합니다. 

int dy[6] = { -2, -2, 0, 0, 2, 2 };
int dx[6] = { -1, 1, -2, 2, -1, 1 };

탐색 범위는 위와 같습니다.

4. 처음 시작하는 노드는 0으로 바꿉니다. ( -1로 채워져있기 때문 )

5. 탐색을 마치고 체스판 배열의 원하는 위치의 가중치를 출력합니다. 다만 입력 받은 도착 위치가 체스판의 범위를 벗어나는 경우가 있을 수 있습니다. 그 경우엔 따로 -1을 출력하게 합니다.

주의할 점

나이트가  이동 할 수 있는 장소가 일반적인 나이트와 다름을 잊으면 안됩니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int dy[6] = { -2, -2, 0, 0, 2, 2};
int dx[6] = {-1, 1, -2, 2, -1, 1};

int n, r1, c1, r2, c2;

bool visit[204][204];
vector<vector<int>>v;



void bfs(int y, int x)
{
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	v[y][x] = 0;
	visit[y][x] = true;
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 6; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= n || ny < 0 || nx < 0 || nx >= n)
			{
				continue;
			}
			if (!visit[ny][nx])
			{
				visit[ny][nx] = true;
				v[ny][nx] = v[y][x] + 1;
				q.push(make_pair(ny, nx));
			}
			//for (int i = 0; i < n; i++)
			//{
			//	for (int j = 0; j < n; j++)
			//	{
			//		//if (r2 == i && c2 == j || r1 == i && c1 == j)
			//		//{
			//		//	cout << "K" << " ";
			//		//}
			//		//else
			//		//{
			//			cout << v[i][j] << " ";
			//		//}

			//	}
			//	cout << "\n";
			//}
			//puts("\n\n\n");
		}

		
	}

}

int main()
{
	cin >> n;
	cin >> r1 >> c1 >> r2 >> c2;
	v.resize(n, vector<int>(n));
	fill(v.begin(), v.end(), vector<int>(n, -1));

	bfs(r1, c1);

	if (r2 >= n || c2 >= n || r2 < 0 || c2 < 0)
	{
		cout << -1;
	}
	else
	{
		cout << v[r2][c2];
	}
	
	return 0;
}

예제 1

7
6 6 0 1

결과 1

예제 2

6
5 1 0 5

결과 2

예제 3

7
0 3 4 3

결과 3