https://www.codingame.com/training/hard/cloudy-weather
설명
- 로봇이 움직이는데 목적지로 가서 수리를 해야함
- 구름을 피해서 출발지점으로 가야함(배터리 상태가 안좋아서 태양에너지가 있을때만 이동가능하고, 구름으로 가려지면 이동을 못함)
- 최단 거리 구하기
접근법
- 단순 BFS로 하기에는 값의 범위가 큼 (10^9)
- 구름의 개수는 250개 이하이나, 값의 범위가 큼(10^9)
- BFS로 접근하되 좌표를 적절히 압축함
- 구름의 시작/끝 + 시작-1/끝+1 을 하면 대략 1000 * 1000 개 정도의 좌표 생성
- 시작 -1, 끝 + 1도 좌표에 추가하는 이유는 우주선이 구름에 바싹 붙어서 가는 경우도 고려하기 위해서임(한 칸 = 압축한 한 칸으로 하고 싶은데, 구름 주변 한 칸도 살리고 싶어서임)
- 1000 * 1000 지도 크기를 대상으로 BFS 실시
- 생성한 지도에서 한 칸의 크기가 서로 달라지는 효과 (10칸을 압축해서 1칸이 되었으면, 지도에서 1칸은 실제 거리 10임)
- 지도에서 구름으로 가려진 부분 체크는 특정 Y 좌표에 대해서 구름으로 가려진 부분을 +1, -1 기법으로 표시하고, 누적합을 구해나가면서 값이 있으면 구름으로 표시하는 접근법을 사용(모든 구름에 대해서 일일이 비교를 하면 250 1000 1000 수행시간으로 시간제한에서 걸림)
- 로봇위치-목적지 BFS를 수행하지만, 각각의 칸의 크기가 서로 다르기때문에 우선순위큐를 사용해야함 : dijkstra 비슷하게
- 제한시간이 빠듯해서 dijkstra에서 A* 알고리즘을 적용해야 시간안에 들어옴
- A* 사용을 위한 hueristic function : 목적지 - 현재 지점간의 맨하탄 거리
- 샘플로 주어진 테스트케이스에서 마지막을 통과하지 못해도, 제출하면 100%로 통과하기는 한다.
newbieski