[SWEA 13165번] 최소 이동 거리 - 파이썬(python)

SW Expert Academy

문제

A도시에는 E개의 일방통행 도로 구간이 있으며, 각 구간이 만나는 연결지점에는 0부터 N번까지의 번호가 붙어있다.

구간의 시작과 끝의 연결 지점 번호, 구간의 길이가 주어질 때, 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 출력하는 프로그램을 만드시오.

모든 연결 지점을 거쳐가야 하는 것은 아니다.

입력

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 연결지점 번호N과 도로의 개수 E가 주어진다.

다음 줄부터 E개의 줄에 걸쳐 구간 시작 s, 구간의 끝 지점 e, 구간 거리 w가 차례로 주어진다. ( 1<=T<=50, 1<=N, s, e<=1000, 1<=w<=10, 1<=E<=1000000 )

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 테스트 케이스에 대한 답을 출력한다.

풀이

• 0에서 출발해서 N까지 이동하는 경우의 최소 거리를 구하는 문제이다.
• 먼저 연결된 구간의 정보를 인접리스트로 입력을 받는다.
• DFS를 통해 목적지인 N에 도달하면 리턴하고 도중에 최소합보다 합이 커지면 리턴한다.

코드

def dfs(num, summ):
    global mn
    if summ>mn:
        return
    if num==N:
        mn=min(mn,summ)
        return
    for i in range(len(road[num])):
        if visit[road[num][i][0]]==1:continue
        visit[road[num][i][0]] = 1
        dfs(road[num][i][0],summ+road[num][i][1])
        visit[road[num][i][0]] = 0

T = int(input())
for test_case in range(1, T + 1):
    # N: 마지막 연결지점, E: 도로의 개수
    N, E = map(int, input().split())
    # 연결리스트 만들기
    road = [[] for _ in range(N + 1)]
    for i in range(E):
        # s:시작 e:끝 w:거리
        s, e, w = map(int, input().split())
        road[s].append([e, w])
    visit=[0]*(N+1)
    mn = 21e8

    visit[0]=1
    dfs(0,0)
    print(f'#{test_case} {mn}')