A. 문제설명
16509번: 장군
오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. 10*9 크기의 장기판이 존재
2. 장기게임에서의 상의 이동은 아래와 같이 8방향으로 가능함
3. 물론, 실제 장기게임 규칙과 같이 해당 이동동선에 말이 존재하면 이동할 수 없음
4. 왕과 상의 위치가 각각 주어졌을 때, 상이 최소이동으로 왕을 잡는 경우를 구하라
B. 접근법
BFS
장기말의 이동의 최단동선 중 왕을 잡는 경우를 찾기 위해 BFS로 구현하였다.
일반적이 BFS와 다른 점은 장기말이 8방향으로 이동가능하며, 한번에 직선 1칸, 대각선 2칸을 이동하기 때문에 해당 동선 이동 중 왕이 걸리는 경우를 고려해야 한다는 점이다.
C. 풀이
1. BFS는 처음 상의 위치에서 탐사를 시작
2. 8방향의 상의 이동동선을 고려하여 이동을 시작
3. 8방향 동선의 직선 1칸, 대각선 2칸 중간 왕이 걸리면 해당 동선으로는 이동 불가, 마지막에 왕이 걸리는 경우에는 OK
4. 큐에 좌표를 넣고 빼가며 왕을 잡은 경우 그 횟수를 반환하고, 마지막까지 반복해도 찾지 못할 시 -1 반환
D. 내 코드
