(C++) [백준 16920번] 확장 게임
https://www.acmicpc.net/problem/16920
16920번: 확장 게임
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위
www.acmicpc.net
풀고 나니까 그렇게 어렵지는 않은 문제였는데, 시간 초과때문에 엄청 고생했다. 결국 다른 분께 도움을 얻었다.
내가 처음 생각한 방법은 다음과 같았다.
1. 1번 정점을 BFS를 돌려서 시작점에 추가한다.
2. 해당 정점을 가지고 이동할 수 있는 횟수 S[1]번이 되기 전까지 이동한다.
3. 1,2번을 1~p번에 대해 반복한다.
였는데, 계속 시간 초과가 났다. 나중에 알게 됐는데, 1번 과정에서 1번 정점을 BFS를 돌리는데는 O(NM)만큼의 시간이 필요하고, https://www.acmicpc.net/board/view/78042번과 같은 예제에서는 시간 초과가 나는게 당연했다.
도움을 얻어 생각한 방법은 다음과 같다.
1. 시작 정점 모두를 BFS에 돌리고, 이를 각각 시작 정점에 해당하는 큐에 추가한다.
2. 큐 전체가 빌 때까지 BFS를 돌리는데, 이 때 이동할 수 있는 횟수 S[1]번이 되면 이를 다른 임시 큐에 push한다.
3. 반복문이 한 번 끝나면 임시 큐에있던 원소를 다시 시작 정점에 해당하는 큐에 push한다.
4. 2~3번을 모든 큐가 빌때까지 반복한다.
이렇게 푸니까 바로 통과가 되더라. 엄청 빠른 코드는 아니지만 너무 고생하기도 했고, 어디서 최적화를 해야할지 모르겠어서 최적화는 생략했다...
