대회 풀이

연꽃잎을 노드로 생각하고, 개구리가 이동할 수 있는 연꽃잎 간에 간선을 추가하면 그래프가 형성된다. 이 그래프 상에서 개구리의 시작 연꽃잎을 출발로 해서 어느 연꽃잎까지 방문할 수 있는지 BFS로 탐색을 한 뒤 거리가 가장 먼 지점을 찾으면 된다. 간선이 주어져 있지 않아서, 간선을 찾는 여러 가지 해법이 존재한다.

아래 세 가지는 여러 가지 해법의 시간복잡도이며 어느 방법으로 풀었는지에 따라 점수를 다르게 받게 된다.

1. O(N^2)

   간선을 미리 형성하지 않고, 연꽃잎에서 어느 연꽃잎으로 뛸 수 있는지 모든 경우를 다 따져보는 방식이다. N 개의 노드에 대해 어느 노드로 연결되어있는지 모르므로 N가지 경우를 모두 탐색하기 때문에 시간복잡도는 O(N^2)이다.

2. O(Nr)

   개구리가 가로로 뛰는 경우만 생각하면, 연꽃잎의 세로 선분만 이용해서 간선의 연결 정보를 알 수 있다. 세로 선분들을 x좌표 순으로 정렬하고, y축에 평행한 직선을 왼쪽부터 오른쪽까지 훑으며 알고리즘을 진행한다. 세로 선분을 만나면, 현재 직선에 세로 선분과 겹치는 구간에서 세로 선분간의 길이를 비교해 간선을 추가할 수 있으면 추가한다. 그 후 세로 선분을 직선에 추가한다. 간선 추가 작업은 최대 r번 일어날 수 있으므로 시간복잡도는 O(Nr) 이다. 개구리가 세로로 뛰는 경우도 따져서 BFS에서 사용하는 모든 간선을 형성할 수 있다.

3. (N logN)

   연꽃잎의 크기가 모두 r이므로, 개구리는 연꽃잎의 4개의 꼭지점에서만 뛰어도, 도달 가능한 모든 연꽃잎을 방문할 수 있다. 개구리가 가로로 뛰는 경우만 생각하면 세로 선분들만 따져도 된다. 세로 선분들을 왼쪽에서 오른쪽으로 훑으면서 위 알고리즘에서 사용한 세로 직선을 indexed tree로 관리하면 O(N logN)의 시간복잡도가 된다.