백준 숨바꼭질 시리즈(1697번, 12581번, 13549번, 13913번)(python3)

 

숨바꼭질1 문제 링크: www.acmicpc.net/problem/1697

숨바꼭질2 문제 링크: www.acmicpc.net/problem/12851

숨바꼭질3 문제 링크: www.acmicpc.net/problem/13549

숨바꼭질4 문제 링크: www.acmicpc.net/problem/13913

 

숨바꼭질5 문제 링크: www.acmicpc.net/problem/17071

숨바꼭질6 문제 링크: www.acmicpc.net/problem/17087

 

숨바꼭질 시리즈가 6번까지 있었네요....

 

0부터 M 사이에 수빈이와 동생의 위치가 주어져 있을 때, 수빈이가 조건에 맞게 이동해서 동생을 찾기까지 얼마나 걸리는지, 최단 시간에 찾는 방법의 개수, path 등을 출력하는 시리즈 문제입니다. Solved.ac 기준 실버1 문제인 숨바꼭질1의 경우 M=100,000, 수빈이는 현재 위치 X에서 1초에 X-1, X+1, 2*X 위치로 움직일 수 있습니다. 이러한 조건에서 동생을 찾을 수 있는 최단 시간을 찾아 출력하면 됩니다. 코드는 다음과 같습니다.

 

기본 아이디어는 BFS입니다. 현재 위치 X에서 X-1, X+1, 2*X로 가는 edge가 있고, 각 위치에서 또 3가지 길을 만들고... 하는 방식으로 탐색 범위를 넓혀가다가 동생의 위치가 나오면 거기까지 가는데 걸린 시간을 출력하면 됩니다. 이미 방문한 위치를 다른 방식으로 재방문 했을 경우에는 최단 시간에 방문한 것이 아니므로 그냥 넘어가면 됩니다. 큐에 들어가는 건 현재 위치와 그 곳까지 가는데 걸린 시간입니다. visited는 이 위치를 방문했는지 여부를 저장합니다. 지금 다시 보니 조금 더 이쁘게 코드를 짠다거나... 최적화를 시킬 수 있을 것 같습니다.

 

다음은 숨바꼭질4 문제입니다. 숨바꼭질1과 동일한 조건에서, 찾는데 걸린 최단시간과 함께 어떤 경로를 통해 찾았는지 과정을 모조리 출력하면 됩니다. 코드는 다음과 같습니다.

 

기존 visited가 방문 여부만 저장했다면, 거기에 더해 해당 위치를 방문하기 직전 위치를 함께 저장해줍니다. 다익스트라에서 최단시간에 방문하는 path를 같이 출력하기 위해 직전 위치를 저장하는 것과 비슷할 것 같습니다. Line 12-22를 제외하면 문제 1을 푸는 코드와 거의 비슷합니다. Path를 출력하는데 있어, 최초 수빈이와 동생의 위치가 같을 때는 위치 1개만 출력해야 하기 때문에 이를 고려해서 코드를 짜면 됩니다.

 

숨바꼭질2 문제는 숨바꼭질1과 동일한 조건에서, 최단 시간에 찾는 방법의 수를 같이 출력해야 합니다. 숨바꼭질1, 4는 동생을 찾자마자 while문을 종료시켜도 되는 반면 숨바꼭질2는 찾고 나서도 바로 종료시키면 안 됩니다. 또한, 어떤 위치를 방문했을 때 그 위치를 같은 시간에 재방문했을 경우 가짓수를 추가시켜줘야 합니다. 코드는 다음과 같습니다.

새로운 위치를 방문할 때 방문을 안 했거나, 같은 시간에 재방문했을 때 큐에 새로운 위치를 넣어주고 방문 횟수를 +1 해줘야 합니다. 그래서 Line 17, 18처럼 조건이 조금 추가됩니다. 이번 visited에는 방문 여부 대신 도달 시간과 가짓수를 저장합니다. 그래서 Line 18에서 도달 시간이 0이면 최초 방문, 도달 시간이 0이 아니면서 현재 큐에서 뽑은 길과 같은 시간에 도착했다면 Line 19-21을 수행하는 식으로 코드를 짰습니다.

 

앞서 가능한 가짓수를 모두 세야하기 때문에 동생 위치를 최초로 방문했다고 해서 바로 종료시키면 안 된다고 했는데, 이는 Line 32-34를 통해 해결했습니다. 매 번(...) visited 내 동생 위치를 체크하면서 도달 횟수가 0이 아니고(최단 시간 방문할수 있는 시간을 찾음), 현재 큐에서 체크하고 있는 루트의 시간이 동생 위치를 최초로 방문한 시간보다 크다면 종료시켰습니다. 매 위치에서 BFS를 통해 새로운 위치를 찾아가고 있기 때문에 큐 내 n+1초 걸리는 위치 이후 n초 걸리는 위치가 존재할 수 없기 때문입니다. 따라서 n초에 동생 위치를 찾았는데 현재 큐에서 뽑은 루트가 n+1초에 도착할 수 있는 방법이라면, 더 이상 탐색할 필요 없이 종료시키면 됩니다.

 

마지막 문제는 숨바꼭질3입니다. 이번에는 숨바꼭질1 문제에서 이동 조건이 조금 바뀌었습니다. 현재 위치 X에서 X-1, X+1로 이동하는데는 똑같이 1초가 걸리지만, 순간이동을 이용해 2*X 위치로 이동하는데는 시간 소모가 없습니다. 

조금 무식하게... 이동할 때마다 순간이동으로 갈 수 있는 모든 위치를 큐에 넣습니다. 그리고는 숨바꼭질1에서 하던 대로 BFS 방식으로 탐색하면 됩니다. 시간초과가 나지 않을까 걱정했는데 그런 일은 일어나지 않았네요. 더 좋은 방법이 있나 고민을 좀 해봐야겠습니다. 글 쓰다가 깨달은건데, Line 26-28이 필요없는 부분이네요. 어차피 Line 16-19에서 모든 $X*2^{n}$ 위치를 다 큐에 넣었으니 다시 넣을 필요가 없습니다.

 

숨바꼭질1을 풀었다면 나머지 문제는 조건을 어떻게 코드에 반영할 지 생각해서 풀면 되는 문제입니다. 5-6번도 있던데 시간될 때 풀어봐야겠네요... 이 시리즈 외에 다른 숨바꼭질 문제도 있는데 똑같이 BFS로 풀면 될 것 같아보입니다. 토마토 문제(풀이)도 같이 풀어보세요!