https://www.codingame.com/training/hard/the-labyrinth
LABYRINTH : 미궁
설명
- 주인공이 control room을 찾아서 끄면(?) 그때부터 타이머가 돌아감
- 타이머가 돌기전에 시작지점으로 와야함
- 주인공 주변 5*5만 보여주고 나머지는 안개로 안보이므로 알아서 잘 찾아야함
- 연료가 1200 주어짐 = 1200번 이동 가능
접근법
- control room을 찾기전과 찾은 후로 나눔
- control room을 찾은 후에 약간의 트릭(?)이 필요함
- 타이머는 불가능한 값이 주어지지는 않는 것 같음
- 연료도 잘 쓰면 부족하지는 않은 것 같음
control room을 찾은 후
- C -> 시작점으로 BFS를 수행해서 최단거리를 구하고(구하면서 경로 저장)
- 현재 상태에서 어디로 가야할지 판단해서 간다
- 이때 최단거리 > 알람이면 뭔가 안 구한 부분이 있는 것이니까 안개부분(? 부분)을 더 탐색한다
- 매번 BFS 해도 시간은 괜찮음
control room을 찾는 방법
- 접근 1 : 상/하/좌/우로 갔을때 더 많은 "?"를 열어볼 수 있는 곳으로 이동
- 접근 2 : 접근 1이 안되면, 접근할 수 있는 "?" 중에서 그룹의 크기가 크면서 가까운 곳으로 이동
- 지금까지 열어놓은 맵에서 어딘가는 "?"와 인접한 부분이 있을 것임
- "?" 그룹 구분 하기 + 크기 구하기 (DFS 이용)
구현할때 조심할 점
- 최단 경로를 찾을때 "?"는 이동하지 않는 것으로 해야하지만
- "?" 를 이동해야 하는 경우가 있음 : 접근할 수 있는 "?"를 찾을 때
- control room을 찾아도 알람시간안에 갈 수 있는지 확인해야함(테스트케이스 중에 하나가 중간에 ???가 탐색 사각지대에 있는데 최단거리를 위해 꼭 거쳐가야하는 곳임)
newbieski