취미로 코딩하기

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

이번에 볼 문제는 백준 16509번 문제인 장군이다.
문제는 아래 링크를 확인하자.

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

주어진 상을 규칙에 따라 움직여 왕이 위치한 곳으로 옮길 때 그 움직인 횟수의 최솟값을 구하는 문제이다.

각 칸을 노드로, 어떤 칸에서 다른 칸으로 움직일 수 있는 관계를 (가중치가 없고 방향이 있는) 에지로 나타내면 주어진 문제는 가중치 없는 방향그래프에서의 최단거리 문제로 표현할 수 있다. 이는 BFS를 통해 해결할 수 있다.

상의 움직임과 체스의 나이트의 움직임이 유사하게 느껴질 수 있지만,

상은 문제에 주어진 그림과 같이 움직이는 점선 위에 다른 말이 놓여있을 경우 그 점선을 따라 진행하는 움직임을 할 수 없다는 점(즉, 다른 말을 뛰어넘을 수 없다는 점)이 다르므로 이에 유의해 구현하자. 특히 왕 또한 (상이 아닌) 다른 말에 해당한다는 점을 잊지 말자.

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

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

int sR, sC, eR, eC;
int dist[10][9];
queue<pair<int, int>> que;
int dr[8] = {3,2,-2,-3,-3,-2,2,3};
int dc[8] = {2,3,3,2,-2,-3,-3,-2};
vector<pair<int, int>> chk[8];

void bfs() {
	que.push(make_pair(sR, sC));
	dist[sR][sC] = 1;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			bool overing = 0;
			for (auto &p:chk[i]) {
				int rr = r + p.first, cc = c + p.second;
				if (rr < 0 || rr > 9 || cc < 0 || cc > 8 || (rr == eR && cc == eC)) overing = 1;
			}
			if (overing) continue;
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr > 9 || cc < 0 || 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);

	chk[0].emplace_back(make_pair(1,0));
	chk[0].emplace_back(make_pair(2,1));
	chk[1].emplace_back(make_pair(0,1));
	chk[1].emplace_back(make_pair(1,2));
	chk[2].emplace_back(make_pair(0,1));
	chk[2].emplace_back(make_pair(-1,2));
	chk[3].emplace_back(make_pair(-1,0));
	chk[3].emplace_back(make_pair(-2,1));
	chk[4].emplace_back(make_pair(-1,0));
	chk[4].emplace_back(make_pair(-2,-1));
	chk[5].emplace_back(make_pair(0,-1));
	chk[5].emplace_back(make_pair(-1,-2));
	chk[6].emplace_back(make_pair(0,-1));
	chk[6].emplace_back(make_pair(1,-2));
	chk[7].emplace_back(make_pair(1,0));
	chk[7].emplace_back(make_pair(2,-1));

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

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