[BOJ] 2098 외판원 순회 - python

2098번: 외판원 순회

2098번: 외판원 순회

 

• 풀이 방법

  모든 경로 중에서 최소 cost를 구해야 하니 완전탐색인가? 경로들의 순서를 기록할 필요는 없고 && city가 32개 이하 잖아? ⇒ bitmask 마지막에 다시 제자리로 돌아오니 어차피 순환이잖아? 우리가 원하는거는 그냥 최소 비용이고 → 시작점은 뭐로 하든 상관없음 top-down으로 할 것인가 , bottom-up으로 할 것인가? → 최소 cost를 구할 것이므로 route를 끝까지 파고 들어갔다가 다시 돌아와서 브랜치들 중 최소를 구하는 top-down을 채택하자 cache는 지금 거치는 노드와, visited 두 개를 이용하는 이차배열을 이용하자. return 조건은 1111..1 로 모두 방문했을 때, 이미 dp table이 존재할 때 이외에는 가지가 갈라지는 곳에서 모이는 것들 중 min(최소)값을 구하자

<완전탐색 코드(시간초과)>

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
W = [list(map(int, input().split(" "))) for _ in range(N)]  # 2차원 배열 입력받기
print(W)

# 풀이1. 완전탐색 + 비트마스킹
# 어느 도시에서 출발할지 다 해보기
# 한번 들른 도시는 다시 방문하지 않음 -> visited 비트마스킹 사용
# 종료조건 : 모든 도시를 다 방문했을 때
inf = float('inf')
ans = inf

def find_path(start,end,visited,cost):
    global ans
    VISITED_ALL = (1 << N) -1
    #종료조건 : 모든 도시를 다 방문했을 때
    if visited == VISITED_ALL:
        current_cost = W[end][start] or inf #왜 이렇게 사용??
        ans = min(ans, cost + current_cost)
        return

    else:
    #아직 도시를 다 방문하지 않았을 때
    #완전탐색이니까 모든 가능한 곳을 다 헤집고 다녀야 함
        for city in range(N):
            #조건 : visited 안했고 & W가 0이 아닌 곳
            if (visited & (1 << city)) == 0 and W[end][city] != 0:
                #visited 갱신 visited|1<<m 사용
                #visited |= (1 << city) #여기서 visited를 갱신하게 되면 다른 애들도 다 얘를 쓰므로 무용지물이 된다.
                current_cost = cost + W[end][city]
                find_path(start,city, visited | (1 << city) ,current_cost)

# for문 돌리기 N개의 도시
# find_path(시작,현재방문,visited,비용)
for startCity in range(N):
    find_path(startCity, startCity, (1 << startCity), 0)

print(ans)

<dynamic programming 코드(최종)>

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
W = [list(map(int, input().split(" "))) for _ in range(N)]  # 2차원 배열 입력받기
print(W)

inf = float('inf') #양의 무한대

#풀이2. Dynamic Programming + 비트 마스킹 사용
dp = [[inf] * (1 << N) for _ in range(N)] #자식(비트마스킹) 먼저, 부모(Node) 나중

ALL_VISITED = (1 << N) - 1

#모든 루트를 방문하고, 갈림길에서는 값을 리턴 받아 최소값을 비교하도록 할것임
def dfs(node,visited):
    if visited == ALL_VISITED: #모두 방문했으면 처음 시작인 0으로 다시 돌아가기
        if W[node][0] == 0:
            return inf
        else:
            return W[node][0]
    if dp[node][visited] != inf : #이미 table이 존재하면 그 값 리턴
        return dp[node][visited]
    #이외에는 새로운 dp테이블 갱신 필요
    #언제? - 길이 존재할 때, 처음 방문하는 도시일 때
    for i in range(1,N): #결국 모든 가능한 노드들을 다 방문해봐야 하긴 함
        if W[node][i] != 0 and visited & (1 << i) == 0:
            dp[node][visited] = min(dp[node][visited], dfs(i, visited | (1 << i)) + W[node][i] ) #갈림길에서 받은 값들 중에 min을 뽑아내기 위해 min을 사용했고, 새로운 값 갱신은 dfs재귀호출 + cost로 함
    return dp[node][visited]

print(dfs(0,1)) #0노드에서 출발하고, 0은 방문한 visited를 넘겨줌

얻어가는 것

• Dynamic programming (DP)→ 이전 값을 저장해 놓을 cache가 필요하다.

         : sub problem으로 쪼갤 수 있는가? 진짜 중복 호출되는가?       

 

def dfs(n):
	if dp테이블에 값이 존재하지 않을 때:
		dp[n] = dfs(n-1) + ... 어쩌구 수식 #재귀로 계산

	#dp테이블에 값이 존재할 때
	return dp[n]

 

• top-down : 최종에서부터 시작해서 필요한 것들을 재귀적으로 채워나간다
  bottom-up : 작은 것부터 하나하나 반복문을 이용해 쌓아간다.

 

• global : 전역변수를 함수 내에서 편집할 때
• nonlocal : 전역변수도 아니고 현재 함수 스코프 변수도 아닌 것을 편집할 때

 

• 비트연산

  #원소 추가
  n = 3
  print(bin(0b0010 | (1 << n)))  #  0b1010
  #원소 제거
  n = 3
  print(bin(0b1010 & ~(1 << n)))  #  0b10
  #원소 조회
  n = 3
  print(bin(0b1010 & (1 << n)))  #  0b1000
  #원소 토글 (XOR)
  n = 3
  print(bin(0b1010 ^ (1 << n)))  #  0b10
  ​

느낀점

"210930"

소요 시간 : 7D 이상

• bit-masking을 통해 시간 초과 문제를 해결한다.
• DP.. D지게 어렵다
• top-down, bottom-up 차이점을 정확히 이해하자