[백준 10473][파이썬] 인간 대포 (우선순위 큐를 사용하지 않는 다익스트라)

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

10473번: 인간 대포

다익스트라 알고리즘을 사용하는 문제이다.

 

우선 이 문제는 그래프를 주지 않았기 때문에 우리가 직접 그래프를 만들어야 한다.

 

주어진 정점은 시작점, 도착점, n개의 대포이다.

 

이 정점들의 모든 pair가 그래프의 간선이 된다. 즉 간선의 개수는 (n+2)의 제곱이 되는 것이다. 

 

지금 이 생각까지 코드로 나타내보자.

 

<입력 받는 코드>

import sys
INF=1e9
input=sys.stdin.readline
start=tuple(map(float, input().split()))
end=tuple(map(float, input().split()))
n=int(input())
canons=[start]
for _ in range(n):
    canons.append(tuple(map(float, input().split())))
canons.append(end)
v=len(canons)

참고로 나는 시작점은 리스트의 가장 앞에, 도착점은 리스트의 가장 뒤에 놓았다.

 

모든 입력 값을 받았으면 그래프를 생성한다.

 

<그래프 생성 코드>

#모든 쌍의 점에 대해서 거리 구하기
graph=[[INF]*v for _ in range(v)]
for i in range(v):
    for j in range(v):
        if i==j:
            graph[i][j]=0
        else:
            s_canon=canons[i] #시작 대포 
            e_canon=canons[j] #도착 대포
            distance=((s_canon[0]-e_canon[0])**2+(s_canon[1]-e_canon[1])**2)**0.5 #거리 구하기
            if i==0 or i==v-1: #a에서는 걸어갈 수 밖에 없음
                graph[i][j]=distance/5
            else:
                graph[i][j]=min(distance/5, abs(distance-50)/5+2)

그림 E.1을 보면 우선 출발 노드가 시작점과 도착점이면 다른 모든 점까지 걸어갈 수밖에 없다.

그에 비해 출발 노드가 대포라면 두 가지 선택권이 있는 것이다.

1. 걸어간다.
2. 대포로 가고 걸어간다.

이 둘 중 작은 값을 선택하면 된다.

 

그래프를 생성했다면 이 다음부터는 다익스트라 알고리즘을 적용하면 된다.

 

일반적인 다익스트라 알고리즘은 우선순위 큐(파이썬에서는 heapq)을 사용하는데 보다싶이 간선의 개수가 매우 많다.

 

간선의 개수가 (n+2)의 제곱에 가깝기 때문에 heapq를 사용하는 것보다는 직접 모든 노드에 대해서 최단 거리를 찾는 편이 더 빠를 것이다.

 

물론 우선순위 큐를 사용해도 시간 내에 문제를 해결할 수 있을 것이다.

# 다익스트라 시작
visited=[False]*v #최단 거리 확정 여부
res=[INF]*v
#시작 점은 확정됨
visited[0]=True
res[0]=0
current=0

visited는 최단 거리 확정 여부를 의미한다. visited[i]가 필수라면 i의 최단 거리는 확정된 상태이다.

 

res는 해당 정점까지 도달하는데 걸리는 최단 거리이다. 이를 계속 갱신하는 방식을 사용할 예정이다.

 

current는 가장 최근에 최단거리가 확정된 정점을 의미한다.

 

시작점(a)는 확정된 상태로 시작한다. 이제 도착점(b)까지의 최단 거리를 구할 차례이다.

 

<우선순위 큐를 사용하지 않는 다익스트라>

while(True):
    if visited[v-1]:
        break
    #일단 연결된 노드들 최단거리 갱신
    for i in range(v):
        res[i]=min(res[i], res[current]+graph[current][i])
    #가장 짧은 거리 찾기
    current_distance=INF 
    for i in range(v):
        #아직 거리가 확정나지 않은 노드들 중 가장 짧은 노드
        if res[i]<current_distance and not visited[i]:
            current=i
            current_distance=res[i]
    visited[current]=True
print(res[v-1])

우선 가장 최근에 확정된 정점(current)와 연결된 모든 노드들 까지의 최단 거리를 갱신한다.

 

res의 값이 갱신될텐데 이는 최단 거리를 확정지을 정점의 후보를 등록하는 과정이라고 보면 된다.

    #일단 연결된 노드들 최단거리 갱신
    for i in range(v):
        res[i]=min(res[i], res[current]+graph[current][i])

 

res는 아래 테이블과 같은 모습일 것이다. (비어있는 부분은 INF)

	A	B	C	D	E	F
A	0	7	5
B		0
C			0
D				0
E					0
F						0

res[A][B]와 res[A][C]가 갱신되었고 이는 후보를 의미하지 확정된 거리를 의미하지 않는다.

 

이제 이 후보들 중에서 최단 거리를 갖는 간선을 찾을 차례이다.

    #가장 짧은 거리 찾기
    current_distance=INF 
    for i in range(v):
        #아직 거리가 확정나지 않은 노드들 중 가장 짧은 노드
        if res[i]<current_distance and not visited[i]:
            current=i
            current_distance=res[i]
    visited[current]=True

current_distance보다 작은 값을 발견할 때마다 current와 current_distance를 갱신해나간다.

 

최단 거리가 확정난 간선은 선택하지 않아야 한다. 이미 최단 경로가 확정난 상태에서 의미가 없기 때문이다.

 

반복문이 끝나면 current에는 최단 거리가 확정난 노드가 담겨있을 것이다. visited[current] 값을 True로 바꿔준다.

 

이를 계속 반복하다가 도착점(b)의 최단 거리가 확정나면 그만둔다.

 

<최종 코드>

import sys
INF=1e9
input=sys.stdin.readline
start=tuple(map(float, input().split()))
end=tuple(map(float, input().split()))
n=int(input())
canons=[start]
for _ in range(n):
    canons.append(tuple(map(float, input().split())))
canons.append(end)
v=len(canons)
#모든 쌍의 점에 대해서 거리 구하기
graph=[[INF]*v for _ in range(v)]
for i in range(v):
    for j in range(v):
        if i==j:
            graph[i][j]=0
        else:
            s_canon=canons[i] #시작 대포 
            e_canon=canons[j] #도착 대포
            distance=((s_canon[0]-e_canon[0])**2+(s_canon[1]-e_canon[1])**2)**0.5 #거리 구하기
            if i==0 or i==v-1: #a에서는 걸어갈 수 밖에 없음
                graph[i][j]=distance/5
            else:
                graph[i][j]=min(distance/5, abs(distance-50)/5+2)
# 다익스트라 시작
visited=[False]*v #최단 거리 확정 여부
res=[INF]*v
#시작 점은 확정됨
visited[0]=True
res[0]=0
current=0
while(True):
    if visited[v-1]:
        break
    #일단 연결된 노드들 최단거리 갱신
    for i in range(v):
        res[i]=min(res[i], res[current]+graph[current][i])
    #가장 짧은 거리 찾기
    current_distance=INF 
    for i in range(v):
        #아직 거리가 확정나지 않은 노드들 중 가장 짧은 노드
        if res[i]<current_distance and not visited[i]:
            current=i
            current_distance=res[i]
    visited[current]=True
print(res[v-1])