[BOJ 6601 // C++] Knight Moves

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6601번 문제인 Knight Moves이다.
문제는 아래 링크를 확인하자.

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

6601번: Knight Moves

체스판의 각 칸에서 다른 칸까지 knight가 움직여야하는 각 최소횟수를 Floyd-Warshall을 이용해 전처리하는 것으로 문제를 간단히 해결하자. 체스판의 크기가 충분히 작으므로 Floyd-Warshall이 아닌 다른 방식(BFS 등)을 이용해 전처리를 하여도 무방할 것으로 보인다.

 

격자판 위에서 상하좌우의 움직임을 이용하여 탐색을 할 때 크기 4의 dr과 dc(또는 dx와 dy)배열을 이용해 간단히 구현할 수 있듯이 나이트의 움직임도 크기 8의 배열을 이용해 아래와 같이 편리하게 구현할 수 있다.

 

아래는 제출한 소스코드이다.

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

int dist[64][64];

int dr[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dc[8] = { 2,1,-1,-2,-2,-1,1,2 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dist, 0x3f, sizeof(dist));
	for (int r = 0; r < 8; r++) {
		for (int c = 0; c < 8; c++) {
			int cur = r * 8 + c;
			for (int i = 0; i < 8; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (-1 < rr && rr < 8 && -1 < cc && cc < 8) dist[cur][rr * 8 + cc] = 1;
			}
		}
	}

	for (int k = 0; k < 64; k++) dist[k][k] = 0;

	for (int k = 0; k < 64; k++) {
		for (int r = 0; r < 64; r++) {
			for (int c = 0; c < 64; c++) {
				dist[r][c] = min(dist[r][c], dist[r][k] + dist[k][c]);
			}
		}
	}

	string s1, s2;
	while (cin >> s1 >> s2) {
		int x = (s1[0] - 'a') * 8 + (s1[1] - '1'), y = (s2[0] - 'a') * 8 + (s2[1] - '1');

		cout << "To get from " << s1 << " to " << s2 << " takes " << dist[x][y] << " knight moves.\n";
	}
}