[ BOJ / Python ] 13424번 비밀 모임
이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프는 양방향 인접 리스트로 구현하였다. 이 문제에서는 친구들의 위치를 시작으로 하는 모든 방까지의 최소 거리를 저장하고, 전체 친구들의 위치에서 해당 방까지의 거리의 합을 따로 관리해야 한다. 전체 친구들의 위치로부터 방까지의 거리의 합을 distance라는 리스트에 저장하였다. 그리고 친구 한명 한명에 대한 최소 거리를 저장하기 위한 리스트 dist를 각 친구에 대하여 탐색할때마다 새로 선언해주면서 최소 거리를 저장하고 너비우선탐색을 마치고 나면 distance의 해당 인덱스에 값을 더해주는 방식으로 접근하였다. 너비우선탐색의 while문에서 각 dist에 여러개의 값이 가능할 경우 작은 값을 취하도록 하였다. 마지막에는 distance 리스트를 순회하며 가장 작은 값의 인덱스를 찾아 출력하였다.
- t를 입력받는다.
- t번 반복하는 for문을 돌린다.
-> n, m을 입력받는다.
-> 그래프를 나타낼 리스트 graph를 2차원 리스트로 선언한다.
-> m번 반복하는 for문을 돌린다.
--> a, b, c를 입력받는다.
-->graph[a]
에(b, c)
를 넣는다.
-->graph[b]
에(a, c)
를 넣는다.
-> k를 입력받는다.
-> 친구들의 위치에 해당하는 리스트 friend를 입력받는다.
-> 친구들 전체 거리의 합을 저장하는 리스트 distance를 0 n+1개로 채운다.
-> friend를 순회하는 i에 대한 for문을 돌린다.
--> 친구 하나 하나에서의 최소 거리를 저장할 리스트 dist를sys.maxsize
n+1개로 채운다.
--> 큐로 사용할 리스트 q를 최소힙으로 선언한다.
-->dist[i]
를 0으로 갱신한다.
--> q가 있을 동안 반복하는 while문을 돌린다.
---> length, cur을 q에서 추출한다.
---> 만약 length가dist[cur]
보다 클 경우, 다음으로 넘어간다.
--->graph[cur]
을 순회하는 nxt, l에 대한 for문을 돌린다.
----> tmp에length+l
을 저장한다.
----> 만약 tmp가dist[nxt]
보다 작을 경우,
----->dist[nxt]
를 tmp로 갱신한다.
-----> q에(tmp, nxt)
를 넣는다.
--> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
--->distance[j]
에dist[j]
를 더한다.
-> 최소 거리의 방을 저장할 변수 result를 0으로 선언한다.
-> 거리의 최솟값을 저장할 변수 mn을sys.maxsize
로 선언한다.
-> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
--> 만약 mn이distance[i]
보다 작을 경우,
---> mn을distance[i]
로 갱신한다.
---> result를 i로 갱신한다.
-> i를 출력한다.
Code
import sys
import heapq
t=int(input())
for _ in range(t):
n, m=map(int, input().split())
graph=[[] for _ in range(n+1)]
for _ in range(m):
a, b, c=map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
k=int(input())
friend=list(map(int, input().split()))
distance=[0 for _ in range(n+1)]
for i in friend:
dist = [sys.maxsize for _ in range(n + 1)]
q=[]
heapq.heappush(q, (0, i))
dist[i]=0
while q:
length, cur=heapq.heappop(q)
if length>dist[cur]:
continue
for nxt, l in graph[cur]:
tmp=length+l
if tmp<dist[nxt]:
dist[nxt]=tmp
heapq.heappush(q, (tmp, nxt))
for j in range(1, n+1):
distance[j]+=dist[j]
result=0
mn=sys.maxsize
for i in range(1, n+1):
if mn>distance[i]:
mn=distance[i]
result=i
print(result)
import sys
import heapq
t=int(input())
for _ in range(t):
n, m=map(int, input().split())
graph=[[] for _ in range(n+1)]
for _ in range(m):
a, b, c=map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
k=int(input())
friend=list(map(int, input().split()))
distance=[0 for _ in range(n+1)]
for i in friend:
dist = [sys.maxsize for _ in range(n + 1)]
q=[]
heapq.heappush(q, (0, i))
dist[i]=0
while q:
length, cur=heapq.heappop(q)
if length>dist[cur]:
continue
for nxt, l in graph[cur]:
tmp=length+l
if tmp<dist[nxt]:
dist[nxt]=tmp
heapq.heappush(q, (tmp, nxt))
for j in range(1, n+1):
distance[j]+=dist[j]
result=0
mn=sys.maxsize
for i in range(1, n+1):
if mn>distance[i]:
mn=distance[i]
result=i
print(result)
Author And Source
이 문제에 관하여([ BOJ / Python ] 13424번 비밀 모임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-13424번-비밀-모임저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)