queue(bfs) 2 horse_knight

문제는 더블릿 14 queue(bfs)에 있는 horse_knight입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/horse_knight/horse_knight.php?pname=horse_knight

장기의 마와 체스의 나이트가 있고 이동할 수 있는 방향은 동일한데 마는 가는 길에 장애물이 있으면 갈 수 없습니다.  이때 출발지점부터 모든 칸에 대해 나이트가 마보다 빨리 갈 수 있는 칸의 수를 구하는 것입니다.  두 말 모두 갈 수 없으면 세지 않고 나이트만 갈 수 있는 곳은 나이트가 빨리 갔다고 간주합니다.

여기서는 모든 칸에 대해 라는 말이 있으므로 큐를 이용한 bfs를 씁니다.   각 위치와 각 위치별 이동 카운트를 가진 클래스 이용한 큐를 생성합니다.  그리고 첫번째 위치를 넣습니다.  판의 각 칸에 대해 먼저 나이트와 마가 그 칸까지 갈 때 필요한 카운트를 구합니다.

배열을 2개를 만들고 하나씩 구하면 됩니다.

먼저 나이트에 대해 이동할 수 있는 칸이 판의 범위를 벗어나지 않고 장애물이 없을 경우 그곳으로 이동하며 위치와 카운트를 넣은 클래스 객체(구조체)를 큐에 넣습니다.  그리고 판에도 카운트를 넣습니다.  이 과정을 나이트의 8방향에 대해 해주고 다음 while문을 돌 때 큐에서 하나 빼줘서 같은 과정을 거칩니다.  더 이상 갈 수 있는 방향이 없을 경우 큐에 값이 들어가지 않을 것이고, 큐는 텅 비게 되며 이때 while문을 벗어납니다.

마도 같은 과정을 거치는데 대신 장애물이 있을 경우의 조건을 더해서 이 때에는 갈 수 없다고 판단하므로 큐에 넣지 않습니다.

두 대상에 대해 모두 끝내면 판 배열에는 나이트와 마가 그 칸을 이동할 때 필요한 카운트가 들어가 잇습니다.

배열을 돌면서 나이트의 카운트가 마의 카운트보다 작은 경우, 나이트는 갈 수 있지만 마는 갈 수 없는 경우의 수를 세서 출력하면됩니다.