1/18 Coding Test

✅ Coding Test

🎈 1810 징검다리 달리기 2

징검다리 위를 달리는 경기를 하기로 했다.

징검다리가 놓여 있는 위치는 (x,y) 순서쌍으로 표현되고 시작점은 언제나 (0,0) 원점이다.
경기가 진행되는 동안 현재 위치한 징검다리와 x좌표 차이가 2이하이고 y좌표 차이도 2이하인 징검다리로만 점프할 수 있다. 결승선은 x축에 평행한 직선인데 여러분이 결승선과 y좌표가 동일한 징검다리에 도달하면 결승선을 통과한 것이므로 경기가 끝난다.

징검다리들의 위치가 주어지면 경기에서 승리하기 위해 가장 빠른 경로를 찾아내는 프로그램을 작성하시오. 가장 빠른 경로란 경로를 구성하고 있는 점프들의 길이 합이 최소인 경로이다. (x1, y1)에 위치한 징검다리에서 (x2, y2)에 위치한 징검다리로의 점프는 유클리디안 규칙을 따른다.

입력값으로 징검다리 수 n, 결승선 y좌표 F가 주어지고 둘째 줄부터 n개의 징검다리들의 좌표가 한 줄에 하나씩 주어진다. n의 범위는 [0, 50,000], F나 각 좌표들의 범위는 [0, 1,000,000]일 때 가장 빠른 경로의 길이를 소수 첫째 자리에서 반올림해 정수로 출력하도록 한다.불가능한 경우에는 -1을 출력한다.

import sys, math, heapq
input = sys.stdin.readline

n, f = map(int, input().split())
# 징검다리 별 좌표, 인덱스 저장
location = [(0, 0, 0)]
# 징검다리에서 이동 가능한 타 다리 번호 인덱스, 거리 저장
graph = [[] for _ in range(n+1)]
# 목표지점 인덱스
target = []
for i in range(1, n+1):
    x, y = map(int ,input().split())
    location.append((x, y, i))
    if y == f:
        target.append(i)
visited = set()
# x좌표 이동 확인
location.sort(key = lambda x: x[0])
for i in range(n+1):
    x1, y1, idx1 = location[i]
    for j in range(n+1):
        x2, y2, idx2 = location[j]
        if abs(x1-x2) > 2:
            break
        elif abs(x1-x2) <= 2 and abs(y1-y2) <= 2:
            dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
            graph[idx1].append((idx2, dist))
            graph[idx2].append((idx1, dist))
            if idx1 < idx2:
                visited.add((idx1, idx2))
            else:
                visited.add((idx2, idx1))
# y좌표 비교
location.sort(key = lambda x: x[1])
for i in range(n+1):
    x1, y1, idx1 = location[i]
    for j in range(n+1):
        x2, y2, idx2 = location[j]
        if abs(y1-y2) > 2:
            break
        elif abs(x1-x2) <= 2 and abs(y1-y2) <= 2:
            if idx1 < idx2 and (idx1, idx2) in visited:
                continue
            elif idx1 > idx2 and (idx2, idx1) in visited:
                continue
            dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
            graph[idx1].append((idx2, dist))
            graph[idx2].append((idx1, dist))


def dijkstra():
    INF = int(1e9)
    distance = [INF for _ in range(n+1)]
    distance[0] = 0
    heap = []
    heapq.heappush(heap, (0, 0))
    while heap:
        now_dist, now_node = heapq.heappop(heap)
        if distance[now_node] < now_dist:
            continue
        for next_node, next_dist in graph[now_node]:
            if distance[next_node] > now_dist + next_dist:
                distance[next_node] = now_dist + next_dist
                heapq.heappush(heap, (now_dist + next_dist, next_node))
    answer = INF
    for i in target:
        answer = min(answer, distance[i])
    if answer == INF:
        return -1
    else:
        return round(answer)
print(dijkstra())

< 해설 >

우선적으로 현재 좌표를 담을 자료구조가 필요하고, 이를 탐색마다 매번 비교해줄 작업이 필요하기에 deque 자료구조를 활용해 탐색을 수행해야 겠다고 판단했다.
하지만, 최단 경로를 확인하려면 모든 경우의 수를 탐색해야 하기에 BFS, DFS로는 시간초과가 발생할 수 있다.
따라서 매 탐색마다 Greedy/Back-Tracking한 방법이 필요한데..
이를 해결하고자 다익스트라 알고리즘을 활용해보고자 한다.

다시 풀어보기..
(오답)