[백준] 10971 파이썬

N의 범위가 10까지 밖에 안되기때문에 N!가지의 경우의 수로 모든 경우를 계산할 경우에도 360만 경우의수이다. 따라서 완전탐색으로 문제를 해결하였다.

1. permutation
   먼저 생각난 아이디어는 순열로 경로를 미리 저장하고 그 저장된 경로를 계산하는 방식이다.

import itertools
import sys

input = sys.stdin.readline

n = int(input())
graph =[list(map(int,input().split())) for _ in range(n)]
nPr = list(itertools.permutations([i for i in range(n)],n))

ans = sys.maxsize
for l in nPr:
    cnt = 0
    try:
        for i in range(n-1):
            _from = l[i]
            _to = l[i+1]
            if graph[_from][_to] >0:
                cnt += graph[_from][_to]
            else:
                raise Exception

            if cnt > ans:
                raise Exception

        if graph[l[-1]][l[0]] != 0:
            cnt += graph[l[-1]][l[0]]
        else:
            raise Exception
    except Exception:
        continue

    ans = min(ans, cnt)


sys.stdout.write(str(ans))

경로의 값이 0일경우 갈 수 없다는 조건을 잘 추가해줘야 한다.

2. DFS
   그래프로 연결되어 있기 때문에 DFS로 순회하면서 최솟값을 갱신하면 된다.

순회할때마다 visited 리스트가 변경되어야 하므로 append 함수가 아닌, += 로 새로운 리스트를 만들어줘야 한다.
이 부분이 핵심이다.

즉, visited.append(v)와 visited = visited + [v]는 완전히 다른 연산이다.

첫번째 연산의 경우 visited변수에 대한 주소가 연산 전후 바뀌지 않는다. 하지만 두번째 연산의 경우 visited에 새로운 주소가 담기게 된다.
새로운 주소를 가지고 계산해나가기 때문에 함수가 return되면 새로운 주소로 추가된 [v]는가 사라진 예전 주소가 남아있게 된다.

import itertools
import sys

input = sys.stdin.readline

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

def dfs(first, current, valueSum, visited=[]):
    global ans

    if valueSum > ans :
        return

    visited = visited + [current]
    if len(visited)==n:
        #print(visited)
        if graph[current][first] != 0:
            ans = min(ans, valueSum + graph[current][first])
        return

    for i in range(n):
        if i not in visited:
            if graph[current][i] != 0:
                dfs(first,i,valueSum+graph[current][i],visited)


for i in range(n):
    dfs(i,i,0,[])

print(ans)

1번풀이

2번풀이

1번풀이는 구간정보를 모두 저장하고 꺼내쓰는 방식이기때문에 메모리가 많이 필요하다.