[백준]16948번: 데스 나이트

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

16948번: 데스 나이트

BFS()를 통해 해결한다. 처음 이런 문제를 해결할 때 항상 2개의 2차원 배열을 만들어

방문을 체크하는 배열과 현재 지점까지의 움직인 횟수를 저장하는 배열을 만들어 사용했다.

조금만 더 최적화를 생각하다보니 2차원 배열 하나를 -1로 초기화 해두 시작하면 될 것으로 생각하여 코드를 작성했다.

 

1) 초기 map의 모든 값을 -1로 해둔다. map 배열은 방문 여부와 동시에 현재 지점까지 이동한 횟수를 저장할 것이다.

2) 처음 시작 지점을 0으로 바꾼다.

3) queue에 방문 가능한 지점을 담으면서 다음 방문 가능한 지점을 판단해( map[nextR][nextC] == -1) 방문하지 않았으면 방문하고 해당 지점의 값을 map[nextR][nextC] = map[curR][curC] + 1로 이전 노드까지 경로 횟수에서 +1 증가한다.

4) queue에서 꺼낸 현재 지점이 도착 지점이면 해당 map의 값을 return 아니면 그냥 -1을 return한다.

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


#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

vector<vector<int>> maps;

int dr[6] = { -2, -2, 0, 0, 2, 2 }; // row 방향 direct
int dc[6] = { -1, +1, -2, +2, -1, +1 }; // col 방향 direct

int BFS(int r1, int c1, int r2, int c2, int N)
{
	queue<pair<int, int>> q;
	q.push(make_pair(r1, c1));
	maps[r1][c1] = 0;

	while (!q.empty())
	{
		int curR = q.front().first;
		int curC = q.front().second;
		q.pop();

		if (curR == r2 && curC == c2)
		{
			return maps[curR][curC];
		}

		for (int i = 0; i < 6; i++)
		{
			int nextR = curR + dr[i];
			int nextC = curC + dc[i];
			
			if (0 <= nextR && nextR < N && 0 <= nextC && nextC < N)
			{
				if (maps[nextR][nextC] == -1)
				{
					maps[nextR][nextC] = maps[curR][curC] + 1;
					q.push(make_pair(nextR, nextC));
				}
			}
		}
	}

	return -1;
}

int main(void)
{
	FastIO;

	int N = 0; // 체스판의 크기 N
	cin >> N;
	maps.resize(N, vector<int>(N, -1));

	int r1 = 0, c1 = 0, r2 = 0, c2 = 0; // 데스 나이트 (r1, c1) -> (r2, c2)로 이동
	cin >> r1 >> c1 >> r2 >> c2;

	cout << BFS(r1, c1, r2, c2, N) << "\n";

	return 0;
}