[BaekJoon 7562번] 나이트의 이동(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

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

 

 

[문제 풀이]

 

쉬웠던 문제

BFS 알고리즘으로 풀면 되는데, 하나 주의할 점이 있다.

문제의 그림에서 나이트가 이동할 수 있는 경우의 수를 알려주었다.(8가지)

 

이전의 다른 문제들은 보통 상 하 좌 우의 이동을 했지만

이 문제는 그림에서 주어진 8가지 이동에 따른 다음 좌표를 확인해야한다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

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


int main(void) {
	int N;
	cin >> N; // 테스트 케이스 개수
	for (int i = 0; i < N; ++i) {
		int l; // 체스판의 한변의 길이
		cin >> l;
		
		int dist[301][301] = { 0, }; // 거리 - 이동해야하는 칸
		bool visited[301][301] = { false, };

		queue<pair<int, int>> q;
		int firstx, firsty; // 나이트가 현재 있는 칸
		cin >> firstx >> firsty;
		q.push({ firstx, firsty });

		int finalx, finaly; // 나이트가 이동하려는 칸
		cin >> finalx >> finaly;

		dist[firstx][firsty] = 0;
		visited[firstx][firsty] = true;
		while (!q.empty()) {
			pair<int, int> curlocation = q.front();
			q.pop();
			for (int k = 0; k < 8; ++k) {
				int nx = curlocation.first + dx[k];
				int ny = curlocation.second + dy[k];
				if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
				if (visited[nx][ny]) continue;
				q.push({ nx, ny });
				visited[nx][ny] = true;
				dist[nx][ny] = dist[curlocation.first][curlocation.second] + 1;
			}
		}
		cout << dist[finalx][finaly] << '\n';
	}

	return 0;
}