[고등부] 2025 KOI 2차대회 대비 모의고사 (1회차)

N개의 방이 N-1개의 통로로 연결되어 있으며, 모든 방은 연결되어 있다.
그 중 연결된 방이 단 하나만 존재하는 방은 출구다.
정올이는 숨어있다가 아침이 되면 출구로 탈출하려고 생각했다.

그 때, 최첨단 경비 시스템이 작동하여 정올이가 있는 위치가 적발되었다!
그 순간 모든 출구에서 경비원들이 동시에 출발해 정올이를 잡으러 다가간다.
정올이와 경비원은 모두 같은 속도로 움직이므로, 매 시간 단위마다 한 방에서 다른 인접 방으로 이동이 가능하다.
또한 경비원들은 모두 정올이의 위치를 실시간으로 파악하고 있다.

만약 경비원이 정올이와 같은 방에서 만나거나, 반대 방향으로 서로 같은 통로를 동시에 지나게 된다면 정올이는 경비원에게 붙잡힌다.
반대로 정올이가 경비원에게 잡히지 않고 출구에 도착한다면 즉시 탈출에 성공한다.

정올이가 처음 숨어있던 방이 어디인지에 따라 필요한 경비원의 최소 수가 달라진다.
각 방에 대하여 경비원을 최적으로 배치했을 때 필요한 최소 경비원의 수를 알아보자.