[platinum3][해설,분류 미확인] 24515 히히 못가

 

https://www.acmicpc.net/problem/24515

소마 면접 준비로 너무 바빠서 브론즈로 스트릭을 연명하였고... 드디어 면접이 끝나 문제풀이를 시작할 수 있게 되었다.

나름 면접에서 내 장점을 어필하려고 최선을 다했고, 워낙 대단한 분들이 많기 때문에 결과가 어떻든 납득할 수 있을 것 같다... 

 

매우 특이한 다익스트라 문제였다. 처음엔 dp 인줄 알고 경계값 문제로 고민했지만... 생각해보니 다익으로 간단히 (구현은 힘들지만) 해결 가능하다.

 

우선 R은 좌측 맨위, J  는 우측 맨아래에 있는데 이둘을 못만나게 하려면 어떻게 이어야 할까?

 

파란 집합 중 아무 점에서 시작하고, 빨간 집합 중 아무 점으로 도착하면  무조건 R , J 를 나눌 수 있다.

 

그렇다면, R , J 를 나눌 수 있는 영역들은 다음과 같다.

 

1.파란 점들 중 아무거나 포함한 영역

2. 빨간 점들 중 아무거나 포함한 영역

3. 1번과 2번을 잇는 나머지 영역들

 

1 + 2 + 3 의 영역이면 R, J를 나눌 수 있을 것이다.

 

시작지점과 도착지점이 명확하고, 최소한의 영역으로 가야한다...  그리고 1번 2번 3번의 모든 영역들은 모두 연결되어 있어야 한다.... 

 이 부분에서 직관적으로 다익스트라가 떠오를 수 있다.   한 영역에서 다른 영역으로 가는 것은 간선으로 생각하고, 그때의 간선의 비용은 다른영역의 넓이 라고 생각할 수 있다. 

그림으로 한번에 보면 이렇다. 4,5,9 에 대해서만 생각해보면 다음과 같다.

 

즉 오른쪽과 같이 그래프로 나타낼 수 있게 된 것이다. 또한 다음간선으로 갈때는 다음으로 가

는 영역의 넓이만큼 더할 것이다. 

처음 pq에는 파란 점을 포함하는 1번, 2번 , 6번 영역을 넣고 시작하고 초기 Cost는 각각 7 , 4 , 4  이다. 그 후 위와 같이 각 영역을 노드로 두고, 다음 영역으로 갈때와, 그때의 비용 (다음 영역의 넓이) 를 간선비용으로 취급하고 다익스트라를 실행한다.

도착지점은  영역 3 , 8 , 9 , 7  중 아무곳이나 도착하면 종료. 그때가 최소 비용으로 R , J 를 분리시킬 수 있다.

 

즉 시작지점과 도착지점이 지정되어 있고, 그 사이를 모두 이어야 하며,  각 영역 사이의 관계는 그래프로 나타낼 수 있으므로, 다익스트라로 구할 수 있는 것이다.

 신박한 다익스트라 문제였다.