99클럽 코테 스터디 1일차 TIL + 백준 11657(벨만-포드)

오늘의 학습 키워드

오늘은 벨만 포드에 대해 배워보았다. 벨만 포드 관련해서 백준 11657 문제를 풀어보았다.

백준 링크 : https://www.acmicpc.net/problem/11657

- 공부한 내용 본인의 언어로 정리하기

# https://www.acmicpc.net/problem/11657
import sys
input = sys.stdin.readline

def bellman_ford(graph,start) :
    distance = [1e9] * (n)
    distance[start] = 0                 # 초기 노드 0 
    
    for i in range(n-1) :
        for start,end,weight in graph :
            if distance[start] != 1e9 and distance[start] + weight < distance[end] :
                distance[end] = distance[start] + weight
        
    for i in range(n-1) :
        for start, end, weight in graph : 
            if distance[start] != 1e9 and distance[start] + weight < distance[end] :
                return -1
    
    return distance


n,m = map(int,input().split())
graph = []
for _ in range(m) :
    a,b,c = map(int,input().split())
    graph.append((a-1,b-1,c))
    
dist = bellman_ford(graph,0)

if dist == -1 :
    print(-1)
else :
    for i in dist[1:] :
        if i == 1e9 :
            print(-1)
        else :
            print(i)

- 오늘의 회고

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

 

우선 이 문제를 항해 취업 리부트 코스를 했을떄 풀어보았던 문제인데.. 다시 풀려고 하니 알고리즘이 떠오르지 않아 못풀었습니다. 그래서 많이 부끄러웠습니다.

 

2. 어떻게 해결했는지

 

벨만포드 알고리즘 학습후 적용해서 다시 풀어보았습니다.

 

3. 무엇을 새롭게 알았는지

 

우선 제가 기억해낸 사실과 알고리즘 공부를 해야 될 떄 명심해야 될 부분을 다시 상기할 수 있었습니다.

• 벨만 포드 알고리즘 : 가중치가 음수일 때 사용합니다
• 알고리즘 공부 : 감을 잃지 말자, 잃어버렸던 내용 다시 상기할 수 있도록 하자