[Python]알고리즘/백준
[DFS/BFS/완전탐색] ★ 10971번 - 외판원 순회 2(DFS, 완전탐색)
[백준] 10971번 - 외판원 순회 2 (한줄평) 설계자체는 단 시간에 했지만 시간초과를 해결하는데 시간이 오래걸렸던 문제로 꼭 복습 필요한 문제!! 이 문제는 외판원 순회 문제(TSP)로 N과 비용행렬이 주어졌을 때 외판원 순회에 필요하 최소 비용을 구하는 것이다. 1 ~ N 번호가 매겨진 도시들을 모두 거쳐 원래의 도시로 돌아오는 순회 여행을 말한다. 완전탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 풀이 시간: 90분 이내 1) 문제 해결 아이디어 1. 비용(graph) 입력 및 이동 경로(temp), 방문 여부(visited)를 저장할 리스트 생성 2. dfs(0, 0) 호출 -> 깊이= 0, 비용= 0으로 시작 3. n개 도시를 다 선택했고 마지막 도시→처음 도시로 가는 비용이 0이 아..
