취미로 코딩하기

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

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

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

체스판 위에서 나이트와 같은 말의 움직임으로 주어진 두 칸 사이를 이동하기 위한 최소 움직임의 횟수를 구하는 문제이다.

각 칸을 노드로, 각 칸에서 움직일 수 있는 다음 (최대) 8가지 움직임을 에지로 하는 그래프로 문제 상황을 모델링하면 주어진 문제는 두 칸을 나타내는 노드 사이의 최단거리와 같음을 알 수 있다. 이 때 모든 에지의 가중치는 같으므로 이 문제는 BFS 등의 알고리즘을 이용해 간단하게 해결할 수 있다.

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

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

int sR, sC, eR, eC;
int dist[9][9];
queue<pair<int, int>> que;
int dr[8] = { 2,1,-1,-2,-2,-1,1,2 };
int dc[8] = { 1,2,2,1,-1,-2,-2,-1 };
void bfs() {
	dist[sR][sC] = 1;
	que.push(make_pair(sR, sC));
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 1 || rr > 8 || cc < 1 || cc > 8 || dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> sR >> sC >> eR >> eC;
	bfs();

	cout << dist[eR][eC] - 1;
}