https://www.codingame.com/training/hard/skynet-revolution-episode-2
- episode1일때는
- 길을 끊어서 바이러스가 gateway까지 못가게 막아야함
- gateway는 한개
- 길은 아무곳이나 끊을 수 있음
- 이때는 바이러스의 현재 위치부터 bfs해서 최단경로에 있는 길을 끊어서 해결했었음
- episode2
- gateway가 여러개(최대 20개)
- gateway와 바로 연결된 길만 끊을 수 있음
접근1
- bfs 수행 후 가까운 gateway근처에 있는 아무 길이나 끊었음
- 실패 : 갈래길에서 한쪽만 끊어서 바이러스가 다른 한쪽으로 가게됨
- 여유가 있게 끊을 수 있는 길이 있고, 미리 끊어야하는 길이 있구나.. 깨달음
접근2
- 끊어야하는 길들이 한 지점에 몰려있는 경우가 있는데, 많이 몰려있는 길 먼저 끊음 + 가까운것 먼저
- 실패 : 여전히 미리 끊어야하는 길이 있었음..여유가 없는 길들
- "여유"를 어떻게 판단해야할지 생각하게됨
접근3
- 여유를 정의 : 어떤 지점까지 최단거리 - 그 지점까지 오면서 만난 끊어야할 길의 개수
- 설명 : 거리가 멀면 그만큼 길을 끊을 수 있는 시간은 많이 주어지지만, 오다가 길을 끊는데 시간을 사용하다보면 정작 남은 시간은 없을 것이다..
- 동일한 여유 값을 가질때 처리 : 지점에 모인 길이 많은 것부터처리
- 실패 : 테케 4까지는 잘 돌아가는데, 진짜 뭐부터 끊어야할지 모르겠음
- 여유가 있는것들이 많을때 누구를 먼저 끊어내야하나..
접근4
- 동일한 여유 값을 가질때 처리 : 지점까지 오면서 만난 끊어야할 길이 많은 것부터처리
- 성공
고민
- 여유가 같을때 왜 접근 4처럼 해야할까..
- 가까운것부터 해도 안됨
- 조금이라도 여유있을때 최선의 선택을 하자? 이런 것 같음
newbieski