[백준/BOJ] 7562: 나이트의 이동

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

7562번: 나이트의 이동

 

 

---

 

 

문제

---

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

 

입력

---

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

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

 

출력

---

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

 

예제 입력

---

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

 

예제 출력

---

5
28
0

 

코드 

---

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

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

void bfs(pair<int, int>& now, pair<int, int>& to_go, int l) {
	queue<pair<int, int>> q;
	int visit[301][301];

	memset(visit, 0, sizeof(visit));

	q.push(now);

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		if (x == to_go.first && y == to_go.second) {
			cout << visit[x][y] << '\n';
			return;
		}
		q.pop();
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx > l - 1 || nx < 0 || ny > l - 1 || ny < 0) continue;
			if (!visit[nx][ny]) {
				q.push(make_pair(nx, ny));
				visit[nx][ny] = visit[x][y] + 1;
			}
		}
	}
}

int main() {
	int t;
	cin >> t;

	while (t--) {
		int l;
		pair<int, int> now, to_go;
		cin >> l;
		cin >> now.first >> now.second;
		cin >> to_go.first >> to_go.second;
		bfs(now, to_go, l);
	}

	return 0;
}

 

 

 

---

 

 

일반적인 BFS문제와 비슷한 문제이다. 다만 이동할 수 있는 경로가 8가지라는 점만 다르다. 큐에 들어있는 front 노드가 이동할 수 있는 8개의 경로에 대해, 방문하지 않은 노드들(visit값이 0)은 방문해주며 좌표를 큐에 넣어주고 visit 값(이동 횟수를 나타냄)은 front노드의 visit 값에 1을 더해준다. BFS를 진행하다가 front의 좌표가 최종적으로 이동해야 하는 목적지의 좌표와 같다면 해당 노드의 visit값을 출력해주고 탐색을 종료한다.