[백준] 10971번(외판원 순회 2)

백준 10971번

최종 제출 코드

n = int(input())
array = [list(map(int, input().split())) for i in range(n)]
stack = []
rows = [False]*n
columns = [False]*n

min_distance = 10000000

def dfs(row):

  global min_distance
  
  if len(stack) == n:
    min_distance = min(min_distance,sum(stack))
    return
    
  for i in range(n):
    if array[row][i] != 0 and rows[row] == False and columns[i] == False:
      stack.append(array[row][i])
      rows[row] = True
      columns[i] = True
      dfs(i)
      stack.pop()
      rows[row] = False
      columns[i] = False

dfs(0)
print(min_distance)

◼ dfs 함수

• 이번에 선택한 원소가 [x, y]일 경우, 다음 원소의 row값은 무조건 y여야 한다
• 이를 인수로 전달하여 해당하는 경우에 대해서만 stack를 생성하도록 한다
• visited 리스트 아이디어를 활용하여 rows와 columns 리스트 생성
• True, False를 체크하여 이미 방문한 장소는 다시 못 들르게 한다
• stack의 길이가 장소의 개수와 같아질 경우 stack의 합을 계산하여 최소값을 갱신한다