백준 1600. 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

bfs로 최단거리를 찾으면 되는데 큐에 {현재 r, 현재 c, 이동횟수, 남은 말의 이동을 할수 있는 횟수 } 를 저장한다. 

이동하는 방향은 총 12방향인데 상하좌우 네방향 + 말의 이동 8방향이다. 

남은 말의 이동을 할수 있는 횟수가 남아 있으면 12방향을 탐색하고, 남아 있지 않으면 네방향만 탐색하면 된다.

 

bfs 문제는 한번 방문한 곳을 다시 방문하지 않도록 하는것이 중요한데, 여기서는 좀 까다로운게 말의 이동 때문에 까다롭다.

단순히 그냥 방문한곳을 다시 방문하지 않도록 하면 안되는데, 그 이유는 한 장소에서 말의이동 횟수가 남은 횟수에 따라 그 후 이동이 달라질수 있기 때문이다. 

 

따라서 K는 최대 30이기 때문에 방문 확인 배열을 mark[k][r][c] 이런식으로 3차원으로 만들어서 (r,c) 좌표에 말의 이동 횟수가 k만큼 남았을때 방문했음을 기록하면 된다.