백준 16509 장군

문제

오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 상을 어떻게 써야 할지 도와주자.

위 그림은 10×9 크기의 장기판을 나타내며, 상은 (5, 4)에, 왕은 (1, 4)에 자리 잡고 있는 기물이다. (0, 3)과 (2, 5)를 꼭짓점으로 하는 사각형과, (7, 3)과 (9, 5)를 꼭짓점으로 하는 사각형은 왕이 위치할 수 있는 궁성이라고 한다. 상은 위 그림과 같이 8가지 방법으로 움직일 수 있는데, 상, 하, 좌, 우로 한 칸을 이동한 후에 같은 방향 쪽 대각선으로 두 칸 이동한다.

만약 상이 이동하는 경로에 위 그림과 같이 다른 기물이 있다면 상은 그쪽으로 이동할 수 없다. 또한, 상이 장기판을 벗어날 수도 없다.

10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수를 구하여라.

입력

첫 번째 줄에는 상의 위치를 의미하는 정수 R1, C1이 주어진다.

두 번째 줄에는 왕의 위치를 의미하는 정수 R2, C2가 주어진다. 장기판에서 Ri (0 ≤ Ri ≤ 9)는 행을, Ci (0 ≤ Ci ≤ 8)는 열을 의미한다.

왕은 항상 궁성에 자리 잡고 있으며, 상과 왕의 위치는 겹치지 않는다.

출력

상이 왕에게 도달할 수 있는 최소 이동 횟수를 출력한다. 만약 도달할 수 없다면 -1을 출력한다.

예제 입력 1 

4 2

2 5

예제 출력 1 

1

---

[풀이 과정]

1. check()

- 현재 상의 위치를 방문 표시 후 q에 현재 위치와 이동 횟수 0을 넣는다.

- q에 값이 있으면 탐색을 시작한다.

- dx, dy를 8x3행렬로 구현했는데 이는 상이 이동하는 중간에 왕이 있으면 그 칸으로는 이동을 못하게 하기 위해서이다. 따라서 이중 for문으로 탐색을 한다.

- 다음 위치가 범위 밖이면 해당 방향은 볼 필요 없으므로 break한다. (이때 break는 j에 대한 break이다.)

- 다음 위치가 왕의 위치인데 중간 이동에 만난거라면 break하고 최종 이동에서 만난거라면 result에 cnt+1을 넣고 true를 리턴해서 탐색을 끝낸다.

- 아직 왕이 나오지 않았고 최동 이동이면 방문 표시 후 q에 값을 넣는다.

- 모든 위치에 대해 탐색을 끝냈는데 왕을 만나지 못하면 false를 리턴한다.

 

2. check의 리턴값이 true이면 왕을 만난것이므로 result를 출력하고 false이면 왕을 만나지 못한 것이므로 -1을 출력한다. 

---

[소스 코드]

#include <cstdio>
#include <queue>
using namespace std;

int sx, sy, kx, ky, result;
int dx[8][3] = { {-1, -2, -3}, {-1, -2, -3}, {0, -1, -2}, {0, 1, 2}, {1, 2, 3}, {1, 2, 3}, {0, -1, -2}, {0, 1, 2} };
int dy[8][3] = { {0, -1, -2}, {0, 1, 2}, {-1, -2, -3}, {-1, -2, -3}, {0, -1, -2}, {0, 1, 2}, {1, 2, 3}, {1, 2, 3} };
bool visited[10][9];

struct info {
	int x, y, cnt;
};

bool check(int a, int b) {
	visited[a][b] = true;
	queue <info> q;
	q.push({ a, b, 0 });

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();

		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 3; j++) {
				int nx = x + dx[i][j];
				int ny = y + dy[i][j];

				if (nx < 0 || nx >= 10 || ny < 0 || ny >= 9) break;

				if (nx == kx && ny == ky) {
					if (j != 2) break;
					else {
						result = cnt + 1;
						return true;
					}
				}

				if (!visited[nx][ny] && j == 2) {
					visited[nx][ny] = true;
					q.push({ nx, ny, cnt + 1 });
				}
			}
		}
	}
	return false;
}

int main() {
	scanf("%d %d", &sx, &sy);
	scanf("%d %d", &kx, &ky);

	if (check(sx, sy)) printf("%d\n", result);
	else printf("-1\n");
	return 0;
}