15004번: Bearly Made It

www.acmicpc.net/problem/15004

15004번: Bearly Made It

시점과 종점, 여러 원들이 주어진다. 시점에서 원 내부만 지나면서 종점에 도착하고자 할 때 최단 경로의 길이 (또는 불가능한지)를 구하면 된다.

 

일단 자명한 점은 시점에서 종점으로 직선으로 가는 경우가 아니라면 최단경로는 무조건 원과 원 사이 교점을 지나야 한다는 것이다. 문제에 제시된 그림에 메모했다. (파랑)

잘 생각해보면 코너를 돌 때 최단으로 이동하는 방법은 코너에 최대한 붙어서 이동하는 것이다. 즉, 코너가 되는 지점인 교점을 지나쳐야 한다.

 

N이 25밖에 되지 않으므로 원들 사이 모든 교점을 구하고, 각 교점들과 시점, 종점을 모두 잇는 선분을 만든다. 선분을 따라 이동하는 최단 경로를 다익스트라 등으로 구할 수 있다. 여기서 각 선분이 가능한지 즉, 원 바깥으로 나가지 않는지 판정하는 것이 중요하다.

 

원과 원 사이 교점을 구하는 식은 여기를 참고하여 O(N^2)으로 모든 원 사이에 교점들을 다 찾았다.(tuple<int, Point, Point> intersect(Circle c1, Circle c2) 함수) 다시 N^2 = M개의 각 교점들을 O(M^2)으로 선분을 만들어보고 가능한지 체크한다.(bool incLine(Line ln, vector<Circle> &cir) 함수) 주의할 점은 시점에서 교점으로, 또는 종점에서 교점으로, 시점에서 종점으로 바로 갈 수도 있으므로 시점과 종점도 포함해서 생각해야 한다. 선분을 만들 수 있다면, 그래프에 간선으로 추가하고 다익스트라를 사용해서 최단 경로를 찾는다.(ld dijkstra(ll start, ll end))

 

최종적으로 시간복잡도는 O(ElogV)인데, 여기서 E = M^2 = N^4, V = N^2 이므로 O(N^4 log N)이다.

 

코드

튜플 처음 배우고 짠거라 함수 생긴게 좀 더럽다...

boj.kr/76c073b38f8d4ec795270874bf90a010

공유 소스 보기

• tuple<int, Point, Point> intersect(Circle c1, Circle c2)
  
  • stackoverflow.com/questions/3349125/circle-circle-intersection-points 을 참고했다.
  • 리턴 튜플의 첫 원소는 교점의 갯수, 두번째와 세번째 원소는 교점이다.
• bool incLine(Line ln, vector<Circle> &cir)
  
  • 선분과 원의 교점을 다 구하고, 정렬한다. 교점들을 스윕하면서 원에 들어가면 depth를 증가하고 원 바깥으로 나가면 depth를 감소한다. depth가 0인 영역 즉, 원 바깥에 있는 영역이 있는지 확인한다. 이 때 주의할 점은 직선이 아니라 선분이므로, 선분의 시작점과 끝점까지만 스윕을 해야 한다.
    
  • 원과 직선의 교점 판정은 이어지는 tuple<int, ld, ld> intersect(Line ln, Circle cc)으로 했다.
• tuple<int, ld, ld> intersect(Line ln, Circle cc)
  
  • math.stackexchange.com/questions/311921/get-location-of-vector-circle-intersection 을 참고했다.
  • 리턴 튜플의 첫 원소는 교점의 갯수, 두번째와 세번째 원소는 교점까지 거리이다.
• ld dijkstra(ll start, ll end)
  
  • 그냥 다익스트라 함수. 자료형만 ld로 바꿨다. 실수 오차 신경 안썼는데 괜찮은 것 같다.