[백준] 11657 타임머신 : Bellman-Ford 알고리즘 그자체인 문제 !

2022. 2. 8. 21:14·Algorithm (PS)
728x90

처음에 타임머신 & 웜홀 문제 컨셉을 이해하는데 응? 시간이 거꾸로 가 ? 무슨말이지;; 이랬는데 이말인 즉슨, 

가중치가 음수일 수 있다라는 의미이다 

즉, 우리는 최단거리를 구해야 하는데, 다익스트라 방법에서는 음수인 value가 주어지지 않았었다. 

음수인 가중치가 주어지면 ?? 바로바로 우리가 알고리즘 시간에 배웠지만 망각했을 가능성이 큰 Bellman-Ford 방법을 떠올려야 한다 !!

다익스트라와 방법은 유사하나, 다른점은 

노드를 하나씩 돌면서, 최단거리를 갱신해주는 작업을 v-1 번만 수행해야 한다는 점이다

v-1 번 이상일때도 값이 바뀐다는 뜻은 바로 cycle을 돌고 있다는 뜻이다 ..

# 11657 타임 머신

n, m = map(int, input().split())
INF = int(1e9)
dist = [INF] * (n+1)
edges = []
for i in range(m):
    a, b, cost = map(int, input().split())
    edges.append((a, b, cost))

dist[1] = 0

def solve():
    for i in range(n):
        for j in range(m): # edges 확인하기 !!!!
            start, end, cost = edges[j][0], edges[j][1], edges[j][2]

            if dist[start] != INF and dist[end] > dist[start] + cost:
                dist[end] = dist[start] + cost
                if i == n-1:
                    return False
    return True

if solve() == False:
    print(-1)
else:
    for i in range(2, n+1):
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])

 

728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 11660 구간 합구하기 -> 다이나믹 프로그래밍으로 효율적인 연산!  (0) 2022.02.13
[백준] 9466 텀프로젝트 : 다익스트라로 왕복하기  (0) 2022.02.10
[백준] 13458번 시험감독 in Python  (0) 2022.02.08
[백준] 10870 피보나치 수열 5  (0) 2022.02.07
정렬 알고리즘  (0) 2022.02.07
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 11660 구간 합구하기 -> 다이나믹 프로그래밍으로 효율적인 연산!
  • [백준] 9466 텀프로젝트 : 다익스트라로 왕복하기
  • [백준] 13458번 시험감독 in Python
  • [백준] 10870 피보나치 수열 5
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • 카카오코딩테스트
  • 쿠버네티스
  • 스파크
  • 리눅스
  • 파이썬
  • dp
  • 백트래킹
  • 데이터엔지니어
  • EC2
  • 클라우드
  • Swift
  • 운영체제
  • 알고리즘
  • dfs
  • 프로그래머스
  • 데이터브릭스
  • 백준
  • BFS
  • AWS
  • 코딩테스트
  • python
  • ansible
  • Kubernetes
  • 데이터엔지니어링
  • Databricks
  • SPARK
  • linux
  • 빅데이터
  • Leetcode
  • docker

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[백준] 11657 타임머신 : Bellman-Ford 알고리즘 그자체인 문제 !
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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