1~N번까지의 헛간 중 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며 하나의 통로는 두 헛간을 연결합니다. 전체 맵에서 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다.
1번헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요
예시 6 7(노드의 개수와 입력할 간선의 수) 3 6 4 3 3 2 1 3 1 2 2 4 5 2
당연히 여기서 모든 헛간은 노드로 헛간의 통로는 간선이 될 수 있습니다.
1번 노드(헛간)로 부터 다른 모든 노드로의 최단 거리를 계산한 뒤에, 가장 최단거리가 긴 노드를 찾는 문제이다. 예를 들어 문제에서의 예제 입력을 그래프로 나타내면 다음과 같이 표현할 수 있다.
출발 노드를 1이라고 조건에서 주어졌으니
| 노드1 | 노드2 | 노드3 | 노드4 | 노드5 | 노드6 |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 2 | 2 |
해당 예시에서 가장 긴 거리는 2인 것을 알 수 있습니다. 최단 거리가 2인 노드가 3개인 것을 알 수 있습니다. 문제에서는 최단거리가 여러개 이을 경우는 첫번째 노드를 반환을 할 것을 조건으로 걸었으니 4번 노드만 출력하면 됩니다.
간선간의 비용이 1이기 때문에 BFS를 통해서도 문제를 풀수도 있지만(큐를 사용하면됩니다) 다익스트라 알고리즘을 이용해봅시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정
#노드의 개수, 간선의 개수를 입력받기
n,m = map(int, input().split())
#시작 노드를 1번 헛간으로 설정
start = 1
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
#최단 거리 테이블을 모두 무한으로 초기화
distance =[INF]*(n+1)
#모든 간선 정보를 입력받기
for _ in range(m):
a,b = map(int, input().split())
#a번 노드와 b번 노드의 이동 비용이 1이라는 의미(양방향)
graph[a].append((b,1))
graph[b].append((a,1))
노드의 개수와 간선의 개수를 입력을 받고 그래프를 초기화를 합니다. 이때 양방향으로 움직일 수 있고 간선의 비용은 1로 통일을 했습니다.
그러면 이렇게 각 노드에서 어디로 갈 수 있는지 들어오게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def dijkstra(start):
q = []
#시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0,start))
distance[start] = 0
while q: #큐가 비어있지 않다면
#가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
dist, now = heapq.heappop(q)
#현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
#현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
#현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost, i[0]))
이제 다익스트라 알고리즘을 봅시다.
먼저 시작노드를 초기화 하는 것으로 시작을하는데 start는 1로 정의했습니다. 그리고 비용은 당연히 0이 됩니다. 이를 큐에 넣는 것으로 시작합시다.
그리고 이제 while을 봅시다. 큐에서 꺼내고 해당 위치에 대해서 이미 처리가 되었다면 무시를 하고 인접한 노드를 순서대로 하나씩 확인을 하고 비용이 더 적은 것이 있다면 이를 갱신을 해서 넣어줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#다익스트라 알고리즘 수행
dijkstra(start)
#최단 거리가 가장 먼 노드 번호(숨을 헛간 번호)
max_node = 0
#도달할 수 있는 노등 중에서, 최단 거리가 가장 먼 노드와의 최단거리
max_distance = 0
#최단 거리가 가장 먼 노드와의 최단 거리와 동일한 최단 거리를 가지는 노드들의 리스트
result = []
for i in range(1,n+1):
if max_distance < distance[i]:
max_node = i
max_distance = distance[i]
result = [max_node]
elif max_distance == distance[i]:
result.append(i)
print(max_node, max_distance, len(result))
마지막으로 최단 거리와 노드를 저장할 변수를 설정을 합니다.
이제 노드를 1번부터 n까지 순회를 합니다.
다익스트라 알고리즘을 통해서 distance는 위처럼 초기화가 되었습니다. 인덱스 4,5,6이 최대 값이 되겠고 가장 먼저오는 4만 리턴을 합니다.
Comments powered by Disqus.