[백준1719] / 택배 - 다익스트라

2024. 11. 12. 16:42·Programming/Algorithm

 

백준1719

 

 

푼 날짜 : 2024.11.12

푼 문제 : [1719] / 택배

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

행렬로 계산하는 거라 처음에는 당황했지만 인덱스 계산만 잘하면 된다!

인덱스 계산 외에는 일반적인 다익스트라와 동일하다. 

대신 이전 위치를 함께 저장해야 하므로 나는 튜플로 저장했다.

 

스페셜 저지 문제이므로 예제 출력과 다르게 나와도 맞는 경우의 수라면 정답처리 된다.

(이런 문구가 없어서 처음에 고민했지만 걱정말고 제출해도 된다!)

 

[ 예제 출력 ]

- 2 3 3 2 2
1 - 1 4 5 5
1 1 - 4 5 6
3 2 3 - 6 6
2 2 3 6 - 6
5 5 3 4 5 -

 

[ 내가 제출한 코드의 출력 ]

- 2 3 3 2 2 
1 - 1 4 5 5 
1 1 - 4 1 6 
3 2 3 - 6 6 
2 2 2 6 - 6 
5 5 3 4 5 -

 

 

3 -> 5 로 이동할 때

빨간 경로처럼 3-1-2-5 로 갈 수도 있고

파란 경로처럼 3-5 로 갈 수도 있다.

 

=> 둘 다 비용은 6으로 동일하기 때문에 둘 다 정답처리 된다!

 

(내)이해를 돕기 위한 이미지

 

 

 

 

코드 :

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

# 어느 집하장에서 왔는지, 가중치(이동에 걸리는 시간)
dist = [[(-1, float('INF')) for _ in range(N+1)] for _ in range(N+1)]

def dijkstra(i, j):
    heap = [(0, i, j)]
    dist[i][j] = (0, 0)

    while heap:
        now_cost, now_y, now_x = heapq.heappop(heap)

        if dist[now_y][now_x][1] < now_cost: continue

        for next_x, cost in graph[now_y]:
            all_cost = now_cost + cost

            if dist[next_x][now_x][1] > all_cost:
                dist[next_x][now_x] = (now_y, all_cost) # (어디서 왔는지, 가중치)
                heapq.heappush(heap, (all_cost, now_x, next_x))

# 각 집하장마다 거리 계산해주기
for i in range(1, N+1): dijkstra(i, i)

# 출력 (어디서 왔는지 출력하면 되므로 0 번째 인덱스 출력)
for i in range(1, N+1):
    for j in range(1, N+1):
        print(dist[i][j][0] if i != j else '-', end=' ')
    print()
print()

 

 

 

차분하게 차근차근 풀어나가면 해결할 수 있다 :)

 

 

'Programming > Algorithm' 카테고리의 다른 글

[백준2211] / 네트워크 복구 - 다익스트라  (1) 2024.11.14
[백준22865] / 가장 먼 곳 - 다익스트라  (0) 2024.11.14
[백준5972] / 택배 배송 - 다익스트라  (0) 2024.11.12
[백준10282] / 해킹 - 다익스트라  (2) 2024.11.12
[백준1238] / 파티 - 다익스트라  (1) 2024.11.12
'Programming/Algorithm' 카테고리의 다른 글
  • [백준2211] / 네트워크 복구 - 다익스트라
  • [백준22865] / 가장 먼 곳 - 다익스트라
  • [백준5972] / 택배 배송 - 다익스트라
  • [백준10282] / 해킹 - 다익스트라
__narrrrrmm
__narrrrrmm
__narrrrrmm
낢
__narrrrrmm
글쓰기 관리
전체
오늘
어제
  • 분류 전체보기 (71)
    • Programming (68)
      • Algorithm (61)
      • React JS (2)
      • SQL (5)
    • 낢의 하루 (1)
    • 대외활동 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

mysql
파싱
그래프탐색
StarRating
DP
백트레킹
프로그래머스
DFS
투포인터
PCCP
Python
Javascript
Dijkstra
최소스패닝트리
파이썬
누적합
다이나믹프로그래밍
삼성 금융아카데미
그래프
다익스트라
알고리즘
컬럼별칭
웹동아리
React.js
백준
MST
BFS
heic
SQL
백트래킹
hELLO· Designed By정상우.v4.5.3
__narrrrrmm
[백준1719] / 택배 - 다익스트라
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.