백준16509 - 장군

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

16509번: 장군

재밌는 문제였다. 상(象)의 위치가 주어지고 왕(王)의 위치가 주어지면 상을 최소 몇 번 이동시켜 왕의 위치까지 도달할 수 있는지 묻는 문제였다. 최소 이동 횟수를 물어보니까 bfs를 이용하여 풀었다.

 

bfs는 총 8방향으로 진행한다. 그리고 상(象)은 진행하려는 방향에 말이 있으면 뛰어 넘지 못한다. 이미 방문한 곳은 체크해줘서 재방문하지 않도록 탐색한다. 탐색 도중에 현재 위치가 왕의 위치라면 앞서 저장한 최소비용과 비교하여 최소비용을 구한다.

 

#include <iostream>
#include <queue>
#define R 10
#define C 9
using namespace std;

//(x, y)까지 총 z번 움직였다.
class Point {
public:
	int x, y, z;
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

int R1, C1, R2, C2; //상(象)의 위치(R1, C1), 왕(王)의 위치(R2, C2)
int small = 987654321; //상(象) -> 왕(王)까지 최소 이동 횟수
bool visit[R][C] = { false, }; //위치 방문여부 체크, 모든 칸은 빈칸이므로 특별히 좌표 공간은 두지 않았다.

//상(象)의 이동방향
int dx[] = { 2,-2,3,-3,2,-2,3,-3 };
int dy[] = { 3,3,2,2,-3,-3,-2,-2 };

void bfs(int x, int y, int z) {
	queue<Point> q;

	//시작하는 위치 넣어주고 방문처리
	q.push(Point(x, y, z));
	visit[x][y] = true;

	while (!q.empty()) {
		//첫번째 원소 추출하고 삭제
		x = q.front().x;
		y = q.front().y;
		z = q.front().z;
		q.pop();

		if (x == R2 && y == C2) { //최종 위치가 왕이면
			small = min(small, z); //최솟값을 구하고
			continue; //다음 큐의 원소로 이동
		}

		for (int i = 0; i < 8; i++) { //8방향 이동
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < R && 0 <= ny && ny < C && !visit[nx][ny]) {
				if (i == 0) { //2 3
					if ((x == R2 && y + 1 == C2) || (x + 1 == R2 && y + 2 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 1) { //-2 3
					if ((x == R2 && y + 1 == C2) || (x - 1 == R2 && y + 2 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 2) { //3 2
					if ((x + 1 == R2 && y == C2) || (x + 2 == R2 && y + 1 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 3) { //-3 2
					if ((x - 1 == R2 && y == C2) || (x - 2 == R2 && y + 1 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 4) { //2 -3
					if ((x == R2 && y - 1 == C2) || (x + 1 == R2 && y - 2 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 5) { //-2 -3
					if ((x == R2 && y - 1 == C2) || (x - 1 == R2 && y - 2 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 6) { //3 -2
					if ((x + 1 == R2 && y == C2) || (x + 2 == R2 && y - 1 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
				if (i == 7) { //-3 -2
					if ((x - 1 == R2 && y == C2) || (x - 2 == R2 && y - 1 == C2)) {
						continue;
					}
					else {
						q.push(Point(nx, ny, z + 1));
						visit[nx][ny] = true;
					}
				}
			}
		}
	}
}

int main() {
	cin >> R1 >> C1;
	cin >> R2 >> C2;

	bfs(R1, C1, 0);

	if (small == 987654321) {
		cout << -1;
	}
	else {
		cout << small;
	}
}