#16509 장군

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

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을 출력한다.

 

풀이

bfs로 구현

상의 이동경로를 다음과 같이 나누었다.

먼저 상 하 좌 우로 한칸씩 이동 하는데 (장애물이 있으면 진행 못함)

상으로 이동시  -> 우상, 좌상 으로 이동 가능

하로 이동시 -> 우하, 좌하 로 이동 가능

좌로 이동시 -> 좌상, 좌하 로 이동 가능

우로 이동시 -> 우상, 우하 로 이동 가능

로 나누어 각각의 이동을 구현하였는데 대각선으로 이동할때 한번은 장애물이 있으면 이동하지 못하게 설정하고 마지막 (2칸) 이동시에 장애물 즉, 왕이 있으면 그때의 시간을 리턴하는 단순 구현문제다.

 

풀이