공부용

https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 풀고 나니까 그렇게 어렵지는 않은 문제였는데, 시간 초과때문에 엄청 고생했다. 결국 다른 분께 도움을 얻었다. 내가 처음 생각한 방법은 다음과 같았다. 1. 1번 정점을 BFS를 돌려서 시작점에 추가한다. 2. 해당 정점을 가지고 이동할 수 있는 횟수 S[1]번이 되기 전까지 이동한다. 3. 1,2번을 1~p번에 대해 반복한다. 였는데, 계속 시간 초과가 났다. 나중에 알게 됐는데, 1번 과정에..