Search

SWEA 1249 보급로

태그
그래프 이론
최단 경로
데이크스트라
생성일
2024/12/11 12:13

문제 설명

•
2차 세계대전의 전투 지역에서 출발지(S)에서 도착지(G)까지 이동하는 도로를 복구하는 데 드는 최소 복구 시간을 계산하는 문제
◦
상하좌우로 이동 가능
◦
파여진 도로의 깊이가 1일 때, 1초의 복구 비용이 발생 (0은 복구 작업 필요 없는 곳)

예제 입력/출력

•
입력1
10 4 0100 1110 1011 1010 6 011001 010100 010011 101001 010101 111010 8 . . .
Plain Text
복사
•
출력1
#1 2 #2 2 . . .
Plain Text
복사

제약 조건

•
∣N∣≤100|N| ≤ 100
◦
NN은 행렬의 크기

문제 풀이

접근1 브루트 포스 - O(4(N×N))O(4 ^ {(N \times N)})
접근2 그리디
접근3 DP
접근4 다익스트라 - O(N2⋅logN)O(N^2 \cdot logN)

풀이 코드

접근4 다익스트라 - O(N2⋅logN)O(N^2 \cdot logN)