[BOJ] 외판원 순회 2

Minsu Han·2022년 12월 14일
0

알고리즘연습

목록 보기
64/105

코드

from sys import stdin, maxsize
input = stdin.readline

def dfs(now, cost, cnt):    # 현재방문중인 도시, 현재까지의 총 비용, 방문한 도시 수
    global ans
    
    if cnt == N:
        if w[now][0]:    # 시작도시로 돌아가는 길이 있는 경우
            cost += w[now][0]    # 돌아가는 비용을 합산
            if cost < ans:        # 최소비용 갱신
                ans = cost
        return

    for i in range(N):
        # 방문하지 않은 도시 중 현재 도시에서 갈 수 있는 도시 방문
        if not visited[i] and w[now][i]:
            # 백트래킹 (dfs 수행후 방문여부 초기화)
            visited[i] = 1
            dfs(i, cost + w[now][i], cnt + 1)
            visited[i] = 0
    
    
# input
N = int(input())
w = [list(map(int, input().split())) for _ in range(N)]

# ans
visited = [0]*N    # 방문여부
visited[0] = 1
ans = maxsize
dfs(0,0,1)
print(ans)

결과

image


풀이 방법

  • 현재 도시로부터 방문 가능한 도시들을 DFS로 방문하며 비용을 계산하고 최소비용을 찾는 문제이다.
  • 모든 도시를 방문한 경우(cnt == N) 시작 도시로 돌아갈 수 있는지 확인하고 가능하다면 시작도시로 돌아가는 비용을 추가한 후 최소비용이라면 갱신한다.
  • 도시를 시작 도시를 제외하고 여러 가지 순서로 방문하기 때문에 현재 도시에서 다른 도시를 DFS로 방문한 이후(DFS return문 수행 후)에는 방문한 도시를 미방문 처리해야한다 (백트래킹)

profile
기록하기

0개의 댓글

관련 채용 정보