[백준/파이썬Python] #2098 외판원 순회 : DFS를 이해합시다. 재귀도 🗺️

🗺️ 문제

https://www.acmicpc.net/problem/2098

• 1~N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있음(길이 없을 수도 있음)
• 외판원이 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 함.
• 한 번 갔던 도시로는 다시 갈 수 없음(출발했던 도시로 마지막에 돌아오는 것은 예외)
• 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우기
• 각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태(도시 i에서 도시j로 가기 위한 비용)
• 비용은 대칭적이지 않음
• 모든 도시간의 비용은 양의 정수
• W[i][i]는 항상 0
• 도시 i에서 도시 j로 갈 수 없는 경우 => W[i][j] = 0
• N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하기

🧠 접근 방법

• 참고 블로그: https://hongcoding.tistory.com/83

• DFS로 경로 탐색
• 방문 기록을 비트마스킹으로 표시

• 참고 영상: https://youtu.be/yHBYeguDR0A(비트연산)

• 각 경로당 최소 비용을 저장(DP)

이 문제는 결국 DFS, 비트마스킹, DP 세가지 개념을 전부 알고 있어야 풀 수 있는 문제입니다. 사실 저는 문제 자체(입력값이 뭔지도...)를 이해 못 했기 때문에 같이 공부하는 분들의 설명을 여러 번 듣고 나서 참고 블로그의 코드가 조금씩 이해되기 시작했습니다. 간단한 비트마스킹 개념과 풀이법을 작성해보겠습니다.

비트 연산자

이 문제는 DFS, DFS 안의 재귀에 대해 이해해야 풀 수 있습니다.

입력

• 첫째 줄: N(도시의 수)
• ~(N개): 비용 행렬

• 항상 순회할 수 있는 경우만 입력으로 주어짐

출력

• 외판원의 순회에 필요한 최소 비용

👩🏻‍💻 코드

DP = [[0 for _ in range((1 << N) - 1)] for _ in range(N)]

행 번호는 도시의 수이고(첫 번째 도시는 0번 도시), 열 번호는 visited입니다. 비트마스킹이 익숙하지 않다면 이 범위를 설정하는 것부터 머리가 복잡해집니다.

    if visited == (1 << N) - 1:
        if graph[start][0]:
            return graph[start][0]
        else:
            return INF

DFS 함수를 돌다가 만약 모든 도시를 방문했다면, 이제 가장 첫 도시였던 0번 도시로 가기만 하면 순회가 끝이 납니다.
그래서 마지막 경로에서 가장 끝(첫 도시)인 0번 도시로 갈 수 있으면 해당 비용을 리턴하고, 아닐 경우에는 무한 값을 리턴합니다.

    if DP[start][visited] != 0:
        return DP[start][visited]

위의 조건에 걸리지 않았다면 DFS 함수를 돌다가 지금 계산하고자 하는 경로의 최소비용이 이미 계산되어 있다면(또 계산할 필요가 없기 때문에 - 메모이제이션), 즉, DP에 값이 저장되어 있다면 해당 값을 리턴합니다.

    DP[start][visited] = INF
    # 도시 가기
    for i in range(1, N): # 0번 도시는 이미 처음에 갔기 때문에
        # 갈 수 없다면
        if graph[start][i] == 0:
            continue
        # 이미 가봤다면
        if visited & (1 << i):
            continue
        DP[start][visited] = min(DP[start][visited], graph[start][i]+DFS(i, visited | (1 << i)))

    return DP[start][visited]

현재 DP 테이블은 0으로 초기화가 되어 있는데 그러면 최소비용을 찾기 위해 min값을 할 때 0 값이 항상 할당되기 때문에 현재 경로의 최소비용을 무한으로 바꿉니다.

• 아직 안 간 경로는 0, 갈 수 없는 경로는 INF, 갈 수 있으며 간 경로는 0과 INF가 아닌 값이라고 생각하면 이해가 빠릅니다.

0번 도시가 첫 도시라고 가정하고 시작했기 때문에 1번 도시부터 for문을 돕니다. 해당 도시를 갈 수 없다면(비용행렬에 값이 0이라면) 넘어가고, 이미 방문한 도시라면 넘어갑니다.

visited & (1 << i)

이 부분은 i를 갔는지 확인하는 부분인데 만약에 i가 1(번 도시)이라고 했을 때 visited와 and 연산을 하면 visited의 1번 부분이 1이여야(1번 도시를 방문했다고 되어 있어야)만 visited & (1 << i) 값이 0이 아닌 값이 나오게 됩니다.

그러면 갈 수 있고, 방문하지 않은 도시에 대해 값이 업데이트됩니다.

DFS(i, visited | (1 << i))

이 부분은 이제부터 갈 경로의 시작(i), 지금 방문 기록에 i 추가한 방문 기록입니다. 예를 들어 i가 1이라면, 1번 도시에 대해 visited와 or 연산을 했을 때 나온 값은 1번 도시가 무조건 1로 바뀝니다. 그러므로 1번 도시에 대해 방문 표시를 해주는 것이 됩니다.

print(DFS(0, 1))

저는 0번 도시부터 시작한다고 가정했기 때문에 0, 1(0번 도시 방문 표시)로 DFS 함수를 실행합니다.

📑 전체 코드

# 외판원 순회 - DP, DFS, 비스마스킹
import sys

N = int(sys.stdin.readline()) # 도시의 수
graph = [] # 비용 행렬 지도
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

INF = float("inf")
DP = [[0 for _ in range((1 << N) - 1)] for _ in range(N)]

def DFS(start, visited):
    if visited == (1 << N) - 1: # 모든 도시를 방문했으면
        if graph[start][0]: # 마지막 경로에서 가장 끝(시작)인 0번 도시로 갈 수 있으면
            return graph[start][0]
        else:
            return INF
    
    # 이미 최소비용이 계산되어 있다면(또 할 필요 없음)
    if DP[start][visited] != 0:
        return DP[start][visited]
    
    DP[start][visited] = INF
    # 도시 가기
    for i in range(1, N): # 0번 도시는 이미 처음에 갔기 때문에
        # 갈 수 없다면
        if graph[start][i] == 0:
            continue
        # 이미 가봤다면
        if visited & (1 << i):
            continue
        DP[start][visited] = min(DP[start][visited], graph[start][i]+DFS(i, visited | (1 << i)))

    return DP[start][visited]

print(DFS(0, 1))