아래는 백준 25953번 템포럴 그래프 문제를 해결하는 예제입니다.
먼저 간단한 입력 예제와 함께, 파이썬 코드(전체 포함) 그리고 각 줄마다 역할, 위치 이유, 실행 흐름, 예제 결과 변화까지 꼼꼼히 설명했습니다.
📌 예제 입력
5 3 6 0 4
0 1 2
1 2 3
2 3 4
3 4 5
0 2 10
1 4 100- 정점 개수 N=5, 시간 단계 T=3, 간선 수 M=6, 출발점 S=0, 도착점 E=4
- 단계마다 동일한 6개의 간선이 발생하며 가중치 그대로 적용됨
전체 Python 코드
import sys
def main():
input_data = sys.stdin.read().split()
# 줄 1: input_data = [ '5','3','6','0','4', ... ]
N, T, M, S, E = map(int, input_data[:5])
# N=5, T=3, M=6, S=0, E=4
edges = list(map(int, input_data[5:]))
# edges = [0,1,2,1,2,3, ...] 6*3*3 values but we read sequential blocks
# dp[t][v]: 시간 t에 정점 v 도달 가능한 최단 거리
INF = 10**18
dp = [[INF]*N for _ in range(T+1)]
# t=0 시점엔 출발점 S에서 거리 0, 나머진 닿을 수 없음
dp[0][S] = 0
# t단계마다 dp[t+1] 갱신
idx = 0 # edges에서 읽기 위한 인덱스
for t in range(T):
# ① 시간 t+1 기본값 = t 시점 그대로 유지
for v in range(N):
dp[t+1][v] = dp[t][v]
# 왜? 걷지 않고 가만히 있는 경우도 valid
# 현재 예: dp[1] = dp[0] -> dp[1][0]=0, 나머지 INF
# ② 간선 M개 모두 탐색
for _ in range(M):
x = edges[idx]; y = edges[idx+1]; w = edges[idx+2]
idx += 3
# 예: 첫 간선 x=0,y=1,w=2
# t 시점에 x에 갈 수 있었다면 y로 이동 고려
if dp[t][x] + w < dp[t+1][y]:
dp[t+1][y] = dp[t][x] + w
# 마찬가지로 y->x
if dp[t][y] + w < dp[t+1][x]:
dp[t+1][x] = dp[t][y] + w
# 이 시점: dp[1][1]=2, dp[1][0]=0
# T 단계 후 도착 E까지 최소거리
ans = dp[T][E]
print(ans if ans < INF else -1)
if __name__ == "__main__":
main()🔍 코드 줄별 설명
1–3행: import sys
- 역할:
sys.stdin.read()로 한 번에 입력을 읽기 위함 - 이 위치: 파일 제일 위, 외부 모듈 선언
- 실행 흐름: 파이썬 인터프리터가 모듈 로딩 시 수행
- 결과 변화: 없음
5행: input_data = sys.stdin.read().split()
- 역할: 모든 입력을 문자열 리스트로 파싱
- 위치 이유: 이후 반복 없이 순서대로 읽기 위해
- 흐름: 입력 전체 "5 3 6 0 4 0 1 2 …" → 분리된 리스트
- 예제:
input_data[0]='5', ..., input_data[5]='0', input_data[6]='1', ...
6행: N, T, M, S, E = map(...)
- 역할: 입력 정보 다섯 개 정수로 저장
- 실행 흐름: 리스트 첫 5요소 → 정수로 변환
- 예제:
N=5, T=3, M=6, S=0, E=4
7행: edges = ...
- 역할: 나머지 입력값 (간선 정보) 리스트 생성
- 위치 이유: 아래 반복문에서 사용하기 위해
- 흐름:
[0,1,2,1,2,3,...]형태 - 예제: 첫값들
edges[0]=0, edges[1]=1, edges[2]=2, ...
10행: INF = 10**18
- 역할: "닿을 수 없음" 판정을 위한 큰 수 정의
- 위치 이유: 상수로 미리 선언
11행: dp = [[INF]*N for _ in range(T+1)]
- 역할: 시간마다 정점별 최소거리 저장 위한 2차원 테이블
- 흐름: 예제선
dp는 4×5 크기, 모두 INF로 초기화
13행: dp[0][S] = 0
- 역할: t=0에서 출발지까지 거리는 0
- 예제:
dp[0] = [0, INF, INF, INF, INF]
16행: idx = 0
- 역할:
edges리스트에서 읽을 위치 추적 - 흐름: 매 간선마다 idx += 3
17~18행: for t in range(T): ...
- 역할: 시간 단계별(dp 갱신) 반복
- 흐름: t=0 → 1 → 2
19~21행: 내부 for v in range(N): dp[t+1][v] = dp[t][v]
- 역할: 가만히 있는 것도 고려
- 예제: dp[1] 초기값은
[0, INF, INF, INF, INF]
24~33행: for _ in range(M): ...
-
역할: 각 단계에서 모든 간선으로 이동 시도
-
위치 이유: 't-1에서 t로의 이동'을 반영
-
흐름:
-
예: t=0, 첫 간선 (0→1, w=2)
- dp[1][1] = min(INF, dp[0][0]+2) = 2
- dp[1][0] = min(0, INF+2) = 0
-
-
다음 간선 처리 반복 → 최종적으로 t=1에서 가능한 정점: 0,1,2 등
36~38행: 결과 출력
-
역할: 도착지까지 최단거리 출력, 불가능하면 -1
-
예제: 3단계 후 E=4까지 도달 가능?
- 실제 경로: 0→1(2)→2(3)→3(4)→4(5): 총 2+3+4+5=14, 단계도 충분하므로 14 출력
✅ 예제 실행 흐름 요약
- t=0 →
dp[0] = [0, INF, INF, INF, INF] - t=1 →
dp[1] = [0,2,5,9,14] - t=2 →
dp[2] = [0,2,5,9,14](간선 동일해 추가 단축 없음) - t=3 →
dp[3] = [0,2,5,9,14] - 최종
dp[3][4] = 14→ 출력 14
🧠 요약 및 팁
-
DP 전개: 시간 축을 따라 상태 전이
-
시간 복잡도: O(T × M + T × N) — 여기서 M ≥ N일 때 약 O(T×M)
-
중요 포인트:
dp[t+1][v] = dp[t][v]: 가만히 있는 선택 허용- 양방향 간선 처리
물론이에요! 아래 코드를 한 줄 한 줄 정말 디버깅하듯 자세히 설명해 드릴게요.
이번에도 예제 입력값을 기억하면서 값의 변화를 단계별로 추적해봅시다.
🔍 현재 우리가 보는 부분
input_data = sys.stdin.read().split()
N, T, M, S, E = map(int, input_data[:5])
edges = list(map(int, input_data[5:]))🧠 디버깅 상황 보고
🎯 input_data = sys.stdin.read().split()
✅ 무슨 역할?
-
sys.stdin.read():- **표준입력(입력파일 또는 터미널)**에서 한 번에 모든 데이터를 문자열 형태로 읽어옵니다.
-
.split():- **공백(스페이스, 줄바꿈 포함)**을 기준으로 나누어 리스트로 만듭니다.
✅ 어디에 있어야 하나요?
- 프로그램이 입력 데이터를 다룰 준비를 시작할 때 가장 위쪽에 둡니다.
- 나중에 반복문이나 계산할 때 사용해야 하므로 가장 초기에 준비해둠.
✅ 실행 흐름에서 무슨 일?
-
프로그램 시작 →
read()호출 → 입력 내용을 한꺼번에 읽고 → 공백 기준 리스트화 -
예를 들어, 입력이:
5 3 6 0 4 0 1 2 1 2 3 2 3 4 3 4 5 0 2 10 1 4 100일 경우:
read()→5 3 6 0 4\n0 1 2\n1 2 3 ...split()→['5','3','6','0','4','0','1','2','1','2','3', ...]
✅ 실제 예제 값 상태:
input_data = [
'5', '3', '6', '0', '4',
'0', '1', '2',
'1', '2', '3',
'2', '3', '4',
'3', '4', '5',
'0', '2', '10',
'1', '4', '100'
]🎯 N, T, M, S, E = map(int, input_data[:5])
✅ 무슨 역할?
-
input_data[:5]:input_data의 0번째~4번째 요소를 슬라이싱 →['5','3','6','0','4']
-
map(int, ...):- 위 슬라이스의 각 원소를
int(정수)로 변환
- 위 슬라이스의 각 원소를
-
대입
N, T, M, S, E = ...:- 변환된 정수를 언팩해서 N,T,M,S,E 각각에 담음.
✅ 위치 이유:
- 가장 맨 앞의 다섯 숫자는 입력 형식에서 항상 고정되어 있으므로 바로 추출.
✅ 실행되는 상황:
-
map(int, ['5','3','6','0','4']) → [5,3,6,0,4]→ 대입:N=5T=3M=6S=0E=4
✅ 요약:
이 한 줄로 맨 처음 5개의 정보를 정리해서 프로그램의 주요 파라미터를 준비합니다.
🎯 edges = list(map(int, input_data[5:]))
✅ 무슨 역할?
-
input_data[5:]:input_data의 6번째 요소부터 끝까지 슬라이싱 →['0','1','2','1','2','3', ...](간선들)
-
map(int, ...):- 각 문자열을 정수 변환
-
list(...):- 정수들을 리스트 형태로 저장
-
이 리스트(
edges)는 나중에idx += 3하면서x, y, w형태로 읽어갑니다.
✅ 위치 이유:
- 문제의 입력 형식에서 5번째 인덱스 이후의 나머지는 전부 간선 정보.
- N,T,M,S,E를 먼저 뽑고 남은 건 다 간선이니 이 부분에서 처리.
✅ 실행되는 상황:
-
예제의 경우:
input_data[5:] = ['0','1','2','1','2','3','2','3','4','3','4','5','0','2','10','1','4','100'] -
map(int, ...) → list(...):edges = [0,1,2,1,2,3,2,3,4,3,4,5,0,2,10,1,4,100] -
나중에
idx = 0 x = edges[idx]; y = edges[idx+1]; w = edges[idx+2]; idx+=3이렇게 3개씩 끊어서 읽습니다.
🎯 한눈에 보기
| 부분 | 값 (예제) | 상태 |
|---|---|---|
input_data | ['5','3','6','0','4','0','1','2','1','2','3', ...] | 리스트(문자열) |
N,T,M,S,E | 5,3,6,0,4 | 정수 |
edges | [0,1,2,1,2,3,2,3,4,3,4,5,0,2,10,1,4,100] | 정수 리스트 |
💡 요약
-
sys.stdin.read().split():- 문자열 리스트를 얻음.
-
map(int, input_data[:5]):- 프로그램의 필수 파라미터 추출.
-
edges = list(map(int, input_data[5:])):- 나머지를 한 번에 정수화 → edges 리스트.
이렇게 준비된 상태에서, 이후 edges를 3개씩 잘라서 x, y, w를 읽으면 됩니다.
혹시 이 부분을 디버깅하면서 출력해보고 싶다면 아래처럼 중간중간 print()를 추가해보시면 좋아요:
input_data = sys.stdin.read().split()
print("DEBUG input_data:", input_data) # 전체 출력
N, T, M, S, E = map(int, input_data[:5])
print("DEBUG N,T,M,S,E:", N,T,M,S,E) # 파라미터 출력
edges = list(map(int, input_data[5:]))
print("DEBUG edges:", edges) # 간선 리스트 출력좋아요! 이번에도 같은 방식으로 한 줄 한 줄 디버깅하듯 꼼꼼히 설명해 드릴게요.
이 부분은 최단 경로 계산을 위한 DP(동적계획법) 테이블을 준비하는 부분이에요.
🔍 현재 코드 부분
INF = 10**18
dp = [[INF]*N for _ in range(T+1)]🧠 디버깅 상황 보고
🎯 INF = 10**18
✅ 무슨 역할?
-
10**18:- 10의 18제곱 →
1,000,000,000,000,000,000(1조의 1000배 = 10억억)
- 10의 18제곱 →
-
이렇게 아주 큰 수를 써서 "무한대" 대신 사용.
-
최단 거리 계산에서 초깃값을 "무한대"라고 두어, 아직 도달하지 못한 정점을 나타냄.
✅ 위치 이유:
- 경로 비용의 최대치를 아득히 초과하게 두어,
min()계산에서 무조건 갱신되도록 함. dp초기화하기 전에 반드시 정의.
✅ 실행 시 무슨 일이 일어나는가?
- 단순히 정수 100경우 저장. 특별히 계산 부담 없음.
- 나중에
dp[t][v]가 아직 도달하지 못한 정점은 이 값(10^18)로 남음.
✅ 예제 상황:
- 문제의 가중치가 100 이하라고 하면 경로 길이는 아무리 길어도 수천~수만 미만인데, INF=10^18은 터무니없이 크므로 "무한대"라고 봐도 무방.
🎯 dp = [[INF]*N for _ in range(T+1)]
✅ 무슨 역할?
-
dp: 2차원 리스트 (행렬) 생성. -
크기 =
(T+1)행 ×N열- T+1행: 0단계(출발)~T단계(마지막 단계)
- N열: 정점 0~N-1
-
초기값을 전부 INF로 채우기.
✅ 어떻게 동작?
for _ in range(T+1)→ 바깥쪽 list comprehension- 안쪽
[*INF]*N→ N개짜리 INF 리스트 생성 - T+1개의 그런 리스트를 바깥쪽 list에 담음
✅ 위치 이유:
- DP 계산을 위해 각 단계마다 정점별 "최단 거리"를 추적해야 함
- 모든 값 초기화 후 시작 정점만 0으로 바꿀 계획
✅ 실행 시 무슨 일이 일어나는가?
예제에서:
- N = 5, T = 3
dp는 4행 5열의 리스트 생성
🎯 디버깅 관점의 상태 확인하기 (예제 기준)
# N=5, T=3 일 때
INF = 10**18
dp = [[INF]*N for _ in range(T+1)]
# dp 상태 출력 디버그
print("DEBUG dp 초기 상태:")
for t in range(T+1):
print(f"t={t}: {dp[t]}")✅ 출력 예상:
DEBUG dp 초기 상태:
t=0: [1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000]
t=1: [1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000]
t=2: [1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000]
t=3: [1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000]이 상태에서 출발 정점만 dp[0][S]=0 으로 바꾼 후 갱신을 시작하게 됩니다.
💡 요약
INF = 10**18: 도달 불가 상태를 나타내는 매우 큰 수.dp = [[INF]*N for _ in range(T+1)]: T+1개 행(시간 단계) × N개 열(정점 수)로 된 2차원 리스트 생성.- 이렇게 준비된 dp 배열은 나중에
dp[t+1][v] = min(dp[t+1][v], dp[t][x]+w)형태의 갱신을 받으며 "최단 거리" 계산에 사용됨.
좋아요! 이제 이 부분을 아주 디버깅 관점에서 자세히 한 줄 한 줄 뜯어서 설명해 드릴게요.
🔍 현재 코드 부분
idx = 0
for t in range(T):
for v in range(N):
dp[t+1][v] = dp[t][v]🧠 디버깅 상황 보고
🎯 idx = 0
✅ 무슨 역할?
idx는edges리스트를 한 줄 한 줄(정확히 3개씩) 읽을 때 사용하는 포인터.- 이 부분에서
idx = 0→edges리스트의 첫 번째 값부터 읽을 준비.
✅ 위치 이유:
edges리스트는 나중에t루프 안에서 단계마다M개의 간선을 3개 묶음(x,y,w)으로 읽어올 거라 시작 전에 초기화.
✅ 예제 값 상태:
edges = [0,1,2,1,2,3,2,3,4,...]idx = 0→edges[0],edges[1],edges[2]를 가장 먼저 읽음.
🎯 for t in range(T):
✅ 무슨 역할?
t= 0, 1, ..., T-1 반복- 각
t단계에서 →dp[t+1]를 계산. - 한 단계 한 단계 "시간이 지나는 것"을 모방.
✅ 위치 이유:
- "T개의 단계"가 있다는 문제 조건을 충족하기 위해.
✅ 실행 시 무슨 일이 일어나는가?
- T=3이면
t=0,1,2를 순서대로 진행 - 한 번 끝나면 다음 단계로 넘어감.
🎯 for v in range(N): dp[t+1][v] = dp[t][v]
✅ 무슨 역할?
v= 0,1,..., N-1 정점에 대해- "정점을 현재 단계에서 안 움직였다면?"를 반영하기 위해
dp[t+1]를dp[t]값으로 채움.
✅ 위치 이유:
- 현재 단계(t)에서 t+1단계로 넘어갈 때 기본값을 미리 채우고, 이후 간선 완화를 하도록 함.
- 이렇게 해야 나중에 "간선 안 타고 대기"한 경우도 유효하게 남음.
✅ 실행 시 무슨 일이 일어나는가?
예제에서 N=5일 경우:
t=0일 때
dp[1][0] = dp[0][0] = 0dp[1][1] = dp[0][1] = INFdp[1][2] = dp[0][2] = INF- ... 나머지도 전부 INF
→ 즉, 간선을 타기 전에는 dp[1]이 dp[0]과 똑같아요.
🔄 전체 디버깅 순서 요약
-
idx=0준비 → edges를 맨 처음부터 읽을 준비 -
t=0단계 시작- dp[1][v] = dp[0][v] → 현재 상태를 한 박자 미뤄서 복사
- (예제: dp[1] = [0,INF,INF,INF,INF])
- 이제 간선을 보며 dp[1]을 갱신
-
t=1단계 시작- dp[2][v] = dp[1][v] 복사
- 그리고 간선 완화
-
t=2단계 시작- dp[3][v] = dp[2][v] 복사
- 그리고 간선 완화
-
t=2끝나면 모든 단계 종료
📝 디버깅 출력 예시 추가
중간 상태를 찍고 싶으면:
idx = 0
for t in range(T):
for v in range(N):
dp[t+1][v] = dp[t][v]
print(f"DEBUG after copying dp[{t}] to dp[{t+1}]:")
print(dp[t+1]) # dp[t+1] 상태 출력예제(T=3,N=5) 기준:
DEBUG after copying dp[0] to dp[1]:
[0, INF, INF, INF, INF]
DEBUG after copying dp[1] to dp[2]:
[0, INF, INF, INF, INF]
DEBUG after copying dp[2] to dp[3]:
[0, INF, INF, INF, INF]이런 디버깅 출력은 "간선을 완화하기 전 상태"를 보여주므로 도움이 됩니다.
좋아요! 아주 자세하게, 주어진 조건과 입력값으로 이 부분이 어떻게 dp 배열을 바꾸는지 한 단계씩, 하나도 빠짐없이 차근차근 디버깅하겠습니다.
초기 세팅
- N=5, T=3, M=6, S=0, E=4
- edges = [0,1,2, 1,2,3, 2,3,4, 3,4,5, 0,2,10, 1,4,100]
- INF = 10**18 (충분히 큰 값)
- dp 배열 크기: (T+1) x N = 4 x 5
- dp는 모두 INF로 초기화 후 dp[0][S=0] = 0
초기 dp 상태
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | INF | INF | INF | INF |
| 1 | INF | INF | INF | INF | INF |
| 2 | INF | INF | INF | INF | INF |
| 3 | INF | INF | INF | INF | INF |
반복문 동작 (for t in range(T): t=0,1,2)
각 단계에서
- 먼저 dp[t+1] = dp[t] 복사 (대기 상태 반영)
- M개의 간선 하나씩 꺼내서 양 방향 완화 (if 조건문으로 갱신)
단계별 디버깅
t=0 시작
1) dp[1] = dp[0] 복사
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | 0 | INF | INF | INF | INF |
2) 간선 M=6개 검사
- idx = 0
| 간선 번호 | x | y | w |
|---|---|---|---|
| 1 | 0 | 1 | 2 |
| 2 | 1 | 2 | 3 |
| 3 | 2 | 3 | 4 |
| 4 | 3 | 4 | 5 |
| 5 | 0 | 2 | 10 |
| 6 | 1 | 4 | 100 |
간선 1: (0,1,2)
-
조건1: dp[0][0] + 2 < dp[1][1] ?
0 + 2 = 2 < INF → True
→ dp[1][1] = 2 -
조건2: dp[0][1] + 2 < dp[1][0] ?
INF + 2 = INF < 0 → False
→ 변화 없음
간선 2: (1,2,3)
-
조건1: dp[0][1] + 3 < dp[1][2]?
INF + 3 = INF < INF → False -
조건2: dp[0][2] + 3 < dp[1][1]?
INF + 3 = INF < 2 → False
간선 3: (2,3,4)
-
조건1: dp[0][2] + 4 < dp[1][3]?
INF + 4 = INF < INF → False -
조건2: dp[0][3] + 4 < dp[1][2]?
INF + 4 = INF < INF → False
간선 4: (3,4,5)
-
조건1: dp[0][3] + 5 < dp[1][4]?
INF + 5 = INF < INF → False -
조건2: dp[0][4] + 5 < dp[1][3]?
INF + 5 = INF < INF → False
간선 5: (0,2,10)
-
조건1: dp[0][0] + 10 < dp[1][2]?
0 + 10 = 10 < INF → True
→ dp[1][2] = 10 -
조건2: dp[0][2] + 10 < dp[1][0]?
INF + 10 = INF < 0 → False
간선 6: (1,4,100)
-
조건1: dp[0][1] + 100 < dp[1][4]?
INF + 100 = INF < INF → False -
조건2: dp[0][4] + 100 < dp[1][1]?
INF + 100 = INF < 2 → False
t=0 종료시 dp[1]
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 10 | INF | INF |
t=1 시작
1) dp[2] = dp[1] 복사
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 2 | 0 | 2 | 10 | INF | INF |
2) 간선 M=6개 검사 (idx 다시 0부터)
간선 1: (0,1,2)
-
조건1: dp[1][0] + 2 < dp[2][1]?
0 + 2 = 2 < 2 → False -
조건2: dp[1][1] + 2 < dp[2][0]?
2 + 2 = 4 < 0 → False
간선 2: (1,2,3)
-
조건1: dp[1][1] + 3 < dp[2][2]?
2 + 3 = 5 < 10 → True
→ dp[2][2] = 5 -
조건2: dp[1][2] + 3 < dp[2][1]?
10 + 3 = 13 < 2 → False
간선 3: (2,3,4)
-
조건1: dp[1][2] + 4 < dp[2][3]?
10 + 4 = 14 < INF → True
→ dp[2][3] = 14 -
조건2: dp[1][3] + 4 < dp[2][2]?
INF + 4 = INF < 5 → False
간선 4: (3,4,5)
-
조건1: dp[1][3] + 5 < dp[2][4]?
INF + 5 = INF < INF → False -
조건2: dp[1][4] + 5 < dp[2][3]?
INF + 5 = INF < 14 → False
간선 5: (0,2,10)
-
조건1: dp[1][0] + 10 < dp[2][2]?
0 + 10 = 10 < 5 → False -
조건2: dp[1][2] + 10 < dp[2][0]?
10 + 10 = 20 < 0 → False
간선 6: (1,4,100)
-
조건1: dp[1][1] + 100 < dp[2][4]?
2 + 100 = 102 < INF → True
→ dp[2][4] = 102 -
조건2: dp[1][4] + 100 < dp[2][1]?
INF + 100 = INF < 2 → False
t=1 종료시 dp[2]
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 2 | 0 | 2 | 5 | 14 | 102 |
t=2 시작
1) dp[3] = dp[2] 복사
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 3 | 0 | 2 | 5 | 14 | 102 |
2) 간선 M=6개 검사 (idx 다시 0부터)
간선 1: (0,1,2)
-
조건1: dp[2][0] + 2 < dp[3][1]?
0 + 2 = 2 < 2 → False -
조건2: dp[2][1] + 2 < dp[3][0]?
2 + 2 = 4 < 0 → False
간선 2: (1,2,3)
-
조건1: dp[2][1] + 3 < dp[3][2]?
2 + 3 = 5 < 5 → False -
조건2: dp[2][2] + 3 < dp[3][1]?
5 + 3 = 8 < 2 → False
간선 3: (2,3,4)
-
조건1: dp[2][2] + 4 < dp[3][3]?
5 + 4 = 9 < 14 → True
→ dp[3][3] = 9 -
조건2: dp[2][3] + 4 < dp[3][2]?
14 + 4 = 18 < 5 → False
간선 4: (3,4,5)
조건1: dp[2][3] + 5 < dp[3][4]?
14 + 5 = 19 < 102 → True
→ dp[3][4] = 19
- 조건2: dp[2][4] + 5 < dp[3][3]?
102 + 5 = 107 < 9 → False
간선 5: (0,2,10)
-
조건1: dp[2][0] + 10 < dp[3][2]?
0 + 10 = 10 < 5 → False -
조건2: dp[2][2] + 10 < dp[3][0]?
5 + 10 = 15 < 0 → False
간선 6: (1,4,100)
-
조건1: dp[2][1] + 100 < dp[3][4]?
2 + 100 = 102 < 19 → False -
조건2: dp[2][4] + 100 < dp[3][1]?
102 + 100 = 202 < 2 → False
t=2 종료시 dp[3]
| t | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 3 | 0 | 2 | 5 | 9 | 19 |
최종 결과
ans = dp[3][4] = 19- 출력:
19
