[백준18223] / 민준이와 마산 그리고 건우 - 다익스트라

2024. 11. 15. 14:24·Programming/Algorithm

 

백준18223

 

 

푼 날짜 : 2024.11.15

푼 문제 : [18223] / 민준이와 마산 그리고 건우

사용한 언어 : python

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

 

 

접근방식 :

두 개의 경로를 계산해서 계산 값이 일치한다면 "SAVE HIM" 아니라면 "GOOD BYE"를 출력했다.

 

1) 민준(1) -> 마산(V)

2) 민준(1)-> 건우(P) -> 마산(V)

 

 

 

코드 :

import sys
import heapq

V, E, P = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(V+1)]
for _ in range(E):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append((B, C))
    graph[B].append((A, C))

def dijkstra(num):
    heap = [(0, num)]
    dist = [float("INF") for _ in range(V+1)]
    dist[num] = 0

    while heap:
        now_cost, now_line = heapq.heappop(heap)
        if dist[now_line] < now_cost: continue

        for next, cost in graph[now_line]:
            all_cost = now_cost + cost

            if dist[next] >= all_cost:
                dist[next] = all_cost
                heapq.heappush(heap, (all_cost, next))
                
    return dist

a = dijkstra(1) 
b = dijkstra(P)

# 마산으로 바로 가는 경우 최단거리
ans1 = a[V]
# 건우에게 갔다가 마산가는 경우 최단거리
ans2 = a[P] + b[V]

print("SAVE HIM" if ans1 == ans2 else "GOOD BYE")

 

 

다익스트라 푸는 재미에 빠져버렸다 :) !!

 

 

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

[백준1261] / 알고스팟 - 다익스트라/그래프탐색  (1) 2024.11.16
[백준23793] / 두 단계 최단 경로 1 - 다익스트라  (3) 2024.11.15
[백준2211] / 네트워크 복구 - 다익스트라  (1) 2024.11.14
[백준22865] / 가장 먼 곳 - 다익스트라  (0) 2024.11.14
[백준1719] / 택배 - 다익스트라  (0) 2024.11.12
'Programming/Algorithm' 카테고리의 다른 글
  • [백준1261] / 알고스팟 - 다익스트라/그래프탐색
  • [백준23793] / 두 단계 최단 경로 1 - 다익스트라
  • [백준2211] / 네트워크 복구 - 다익스트라
  • [백준22865] / 가장 먼 곳 - 다익스트라
__narrrrrmm
__narrrrrmm
__narrrrrmm
낢
__narrrrrmm
글쓰기 관리
전체
오늘
어제
  • 분류 전체보기 (71)
    • Programming (68)
      • Algorithm (61)
      • React JS (2)
      • SQL (5)
    • 낢의 하루 (1)
    • 대외활동 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

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

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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