[백준] 10971 : 외판원 순회 2

문제

개념

DFS

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    # v 노드에서 인접한 노드인 i 노드를 매개변수로 받음
    # 해당 노드를 방문처리 해줌!
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: 
            # v 노드에서 인접한 노드인 i에 더이상 F(방문하지 않은 노드)가 없을 때는 
            # 재귀호출을 더이상 진행하지 않음!
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

global 변수

함수 안에서 함수 밖의 데이터를 변경하고 싶으면 함수 안에 global 키워드를 사용해주어야 한다.

(중요) 매개변수가 아닌 변수로 함수 밖에서 선언해준 값을 함수 안에서 변경하고 싶을 경우, 함수 안에서 global로 선언해줘야 한다.
-> 그래야 변수의 값을 변경 가능!!

>>> a = 0
>>> def func():
...     global a
...     a += 2
... for i in range(10):
...     func()
... print(a)
20

풀이

Python3로 제출하면 시간초과이지만, PyPy로 제출하면 맞았다고 뜸!

import sys

n = int(sys.stdin.readline())

# 2차원 배열 : 각 인덱스는 노드, 그 안의 원소는 다른 노드를 가는 데에 드는 비용
matrix = []
for _ in range(n):
    matrix.append([int(x) for x in sys.stdin.readline().split()])

# minCost는 최소비용을 비교해줘야 하므로 처음엔 무한대로 설정
minCost = float('inf')
visit = [False for _ in range(n)]

def dfs(start, cur, cost):
    global matrix, minCost, visit
    
    if start == cur and visit.count(False) == 0:
        minCost = min(minCost, cost)
    
    # n개의 노드이므로 for i in range(n)
    for i in range(n):
        # 노드 0부터 n-1까지 인접노드를 한바퀴 돎
        if matrix[cur][i] != 0 and visit[i] != True:
            visit[i] = True
            # 상향식 분석으로 봤을 때, cost에 matrix[cur][i]가 계속 쌓임! (누적됨)
            dfs(start, i, cost+matrix[cur][i])
            # 재귀가 끝났을 때 전역변수인 visit[i]를 False로 초기화해둬야 다음 인접노드 돌 때 잘 돎
            visit[i] = False
            # 재귀가 끝나면 다음 코드가 실행되므로 False를 하나씩 실행해주면서 모두 False로 만들어줌!
    
dfs(0, 0, 0)
print(minCost)

풀이 2.

permutations 조합 라이브러리를 사용해서 푼 풀이

import sys
import itertools

n = int(sys.stdin.readline())
clist = [i for i in range(1,n)]
minCost = 9999999
matrix = []
for i in range(n):
    matrix.append(list(map(int, sys.stdin.readline().split())))
    
perm = list(itertools.permutations(clist, len(clist)))

for i in range(len(perm)):
    cost = []
    for j in range(len(perm[i])+1):
        if j == 0:
            cost.append(matrix[0][perm[i][j]])
        elif j == n - 1:
            cost.append(matrix[perm[i][j-1]][0])
        else:
            cost.append(matrix[perm[i][j-1]][perm[i][j]])
    
    if 0 not in cost: 
        # 확실하게 cost에 0이 있는지 아는 방법은 cost를 배열로 만들고 각 배열의 원소로 cost를 넣어준 다음, 0이 존재하는지 보는 것!
        minCost = min(minCost, sum(cost))

print(minCost)

DFS 사용하여 시간초과 안 나는 풀이

위에 DFS를 사용한 풀이는 모두 PyPy를 사용해줘야 시간초과가 나지 않았다.
Python으로도 시간초과가 나지 않고 문제를 풀기 위해

dfs 함수 맨 위에 이미 현재 cost가 minCost보다 크다면 return을 해주어 더이상 재귀함수가 돌지 않도록 했다.

그랬더니 Python으로 풀 수 있을뿐만 아니라, 시간도 1684ms 정도에서 292ms 정도로 약 7배 정도 줄었다!!!!!
(획기적)

앞으로도 min이나 max 값을 구할 때 맨 위에 이런 조건들을 두고 맞지 않는다면 바로 return을 해주는 게 시간복잡도 측면에서 매우 효율적일 것 같다!

import sys

n = int(sys.stdin.readline())
matrix = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
minCost = 9999999
visited = [False] * n # False가 아직 방문하지 않은 상태

def dfs(cur, cost):
    global minCost, visited
    
    # 이미 최솟값 아니라면 바로 리턴
    if cost > minCost :
        return
    
    # 다 돌았을 때
    if cur == 0 and visited.count(False) == 0:
        minCost = min(minCost, cost)
        return
    
    for i in range(n):
        if matrix[cur][i] != 0 and visited[i] == False:
            visited[i] = True
            dfs(i, cost + matrix[cur][i])
            visited[i] = False


dfs(0, 0)
print(minCost)