• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

(작성중)[백준] 10971 : 외판원 순회 2 with python3

18 Aug 2019

Reading time ~2 minutes

문제 : https://www.acmicpc.net/problem/10971

목표 :

  • 외판원이 가장 적은 비용으로 모든 도시 도는 것

조건 :

  • 도시의 수는 2 <= N <= 10
  • 한번 간 도시는 돌아오는 것이 아닌한 가지 않는다.
  • 0으로 된 곳은 갈 수 없는 곳이다.

푸는법 :

  • dfs
  • permutation으로 완전 탐색을 하는 것이다.

dfs로 푸는 법

  • 사실 왜 답인지 모르겠다 (…)
  • 왜 cnt가 n인 것은 3번 밖에 안되는지…. 의문 ㅜㅜ
  • 이거 아시는 분 덧글 좀 주세요
  • 참고자료 :https://blockdmask.tistory.com/229
import sys
sys.setrecursionlimit(10**6)
n = int(input())
arr = [list(map(int,input().split()))for _ in range(n)]
ret = sys.maxsize

visited=[-1]*n

def dfs(start, x, res, cnt):
    global ret
    if cnt == n and start == x : # 다 돌았고, 다시 돌아왔음
        ret = min(ret, res) # 총 값중에서 ret이랑 비교 -> dfs는 각 위치마다 시작한다

    for y in range(n):
        if (visited[y] != -1 or arr[x][y] == 0) : continue
        visited[y] = 1
        res += arr[x][y]

        if res <= ret:
            dfs(start, y, res, cnt+1)
        visited[y] = -1 # visited 다 초기화
        res -= arr[x][y] # res도 초기화

for i in range(n):
    dfs(i, i, 0, 0)
print(ret)

permutation

  • 일단 brute force로 다 해보는 것이다
  • if i[0] != 0: break는
    • 자바나 cpp은 이거 없어도 되는데 파이선은 안된다.
    • 근데 왜 되는 걸까?
    • (1, 0, 2, 3) 과 (0, 1, 3, 2)이 같기 때문일 것 같다.
    • 맞는 생각일까… 어차피 0을 시작점으로 모든 경우의 수 다 해봤으니 되는 것 같다.
from itertools import permutations
import sys
N = int(input())
NPerm = [*permutations(list(range(N)))]

W = [list(map(int, input().split())) for _ in range(N)]
ans = sys.maxsize

for i in NPerm: #permutation을 돌린다.
    sums = 0 # 일단 sums에 값을 차곡차곡
    ok = True
    for j in range(N-1):
        cost = W[i[j]][i[j+1]] # permutation에서 정한 값들을 돈다.
        if cost == 0: # cost가 0이나오면 그길로는 못간다.
            ok = False
        else: sums += cost
    if ok and W[i[N-1]][i[0]] != 0:
         # W[i[N-1]][i[0]] != 0 이건 돌아오는 길이 존재하는 것 확인하는 것
        sums += W[i[N-1]][i[0]]
        ans = min(ans, sums)
    if i[0] != 0: break

print(ans)


algorithm백준python Share Tweet +1