Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 브루트포스
- 시뮬레이션
- 구현
- 투포인터
- 스택
- 다익스트라
- 비트마스킹
- 2020 KAKAO BLIND RECRUITMENT
- GIT
- BFS
- 조합
- 2020 카카오 인턴십
- 파이썬
- 프로그래머스
- 최소 신장 트리
- 로봇 청소기
- 2018 KAKAO BLIND RECRUITMENT
- 투 포인터
- 백트래킹
- SWEA
- 트라이
- 플로이드 와샬
- 이분탐색
- 크루스칼
- 우선순위큐
- 2021 KAKAO BLIND RECRUITMENT
- 2019 KAKAO BLIND RECRUITMENT
- 플로이드와샬
- Spring
- 백준
Archives
- Today
- Total
개발조아
[BOJ/백준] 네트워크 복구 파이썬 본문
728x90
문제 링크 : https://www.acmicpc.net/problem/2211
처음에는 문제의 조건이 좀 어려웠었다. 하지만 결국 최소한의 비용으로 최소한의 개수로 연결해라인데
결국 다익스트라를 사용하면 된다.
다익스트라로 각 점마다의 최단경로를 구할 수 있다. 하지만 경로를 저장해야한다.
그래서 나는 비용과 연결된 이전 노드를 저장했다.
2번 노드에서 3번노드로 연결되어있고 비용이 1이라면
배열[3] = (2,1)
이런식으로 저장된다.
그래서 3번노드는 2번 노드와 연결되어 있다는 의미이다.
그래서 1을 제외한 노드에서 거꾸로 타고 들어가보면 결국 1로 도달하게 된다.
이때의 점들을 기록하여 주면 된다.
주의할점은 점들이 중복해서 나오므로 set을 이용하여 중복을 제거해주자.
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
INF = 9876543210
n,m = map(int, input().split())
adj_list = [[] for _ in range(n+1)]
for _ in range(m):
a,b,c = map(int, input().split())
adj_list[a].append((b,c))
adj_list[b].append((a,c))
def solv():
visited = [[INF,-1] for _ in range(n+1)]
pq = [(0,1)]
visited[1] = [n+1,0]
while pq:
cost,now = heappop(pq)
for nxt,nxt_cost in adj_list[now]:
if visited[nxt][0] == INF or visited[nxt][1] > cost+nxt_cost:
visited[nxt] = [now,cost+nxt_cost]
heappush(pq,(cost+nxt_cost,nxt))
answer = set()
for now in range(2,n+1):
nxt = visited[now][0]
while nxt != n+1:
answer.add((now,nxt))
now = nxt
nxt = visited[now][0]
print(len(answer))
for a,b in answer:
print(a,b)
solv()
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ/백준] 1162 도로포장 파이썬 (0) | 2021.09.17 |
---|---|
[BOJ/백준] 1719 택배 파이썬 (0) | 2021.09.17 |
[BOJ/백준] 4485 녹색 옷 입은 애가 젤다지? 파이썬 (0) | 2021.09.16 |
[BOJ/백준] 16509 장군 파이썬 (0) | 2021.09.14 |
[BOJ/백준] 9519 졸려 파이썬 (0) | 2021.09.14 |
Comments