[백준 알고리즘] 10971 Python 풀이

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

 

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

 

 

백준 알고리즘 10971번

 

 

사실 이 문제는 더이상 완전 탐색으로 풀리지 않는 것 같다. 처음에 순열을 이용한 완전탐색을 시도했다가 시간초과가 나와서 2020년 3월에 작성된 다른 분의 DFS 풀이로 다시 한 번 풀었는데 이 코드도 시간초과를 받았다. 결국 또 다른 분의 비트마스크를 활용한 풀이를 참조해 성공 결과를 받을 수 있었다.

 

첫 번째 풀이 (순열을 활용한 완전 탐색) - 시간 초과

라이브러리를 사용하지 않고 순열을 구하려면, 나리야나 판디타의 다음 순열 알고리즘을 사용해 구현할 수 있다.
다음 순열 알고리즘 10972번과, 10974번을 참고
sdesigner.tistory.com/49
sdesigner.tistory.com/50

도시 방문 순서를 순열로 모든 경우의 수를 탐색하고, 각각 비용을 구해 최솟값을 찾아낸다.

# 오답 : 시간초과
import sys


def next_permutation(object_list):
    k = -1
    m = -1
    for i in range(len(object_list)-1):
        if object_list[i] < object_list[i+1]:
            k = i

    if k == -1:
        return -1

    for i in range(k+1, len(object_list)):
        if object_list[k] < object_list[i]:
            m = i

    object_list[k], object_list[m] = object_list[m], object_list[k]

    object_list = object_list[:k+1] + sorted(object_list[k+1:])
    return object_list


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

# 입력 저장: 쉬운 인덱싱을 위해 0행, 0열 임의로 삽입(0행: [], 0열: -1)
w= [[]]
for _ in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    row = [-1] + row
    w.append(row)


# permutation: 도시 방문 순서를 담는 리스트
permutation = [i for i in range(1, n+1)]
ans = 10000000

# 도시 방문할 때마다, 해당 w값을 합산(s)
s = 0
for i in range(n-1):
    # 갈 수 없는 경로인 경우 최댓값을 주어 ans 변경하지 않도록 처리
    if w[permutation[i]][permutation[i+1]] == 0:
        s = 10000000
    s += w[permutation[i]][permutation[i+1]]

# 순회이므로 마지막 도시에서 처음 도시로 오는 w값 추가
s += w[permutation[-1]][permutation[0]]

# ans 값 업데이트
if s < ans:
    ans = s


# 모든 도시 방문 순서를 탐색하며 ans 값 업데이트
result = permutation
while True:
    result = next_permutation(result)
    if result == -1:
        break

    s = 0
    for i in range(n-1):
        # 갈 수 없는 경로인 경우 최댓값을 주어 ans 변경하지 않도록 처리
        if w[permutation[i]][permutation[i + 1]] == 0:
            s = 10000000
        s += w[result[i]][result[i+1]]

    s += w[result[-1]][result[0]]
    if s < ans:
        ans = s

print(ans)

 

 

두 번째 풀이 (DFS를 활용한 완전 탐색) - 시간 초과

풀이 출처 : https://jjangsungwon.tistory.com/4

def dfs(start, next, value, visited):
    global min_value

    if len(visited) == N:
        # 마지막 도시에서 시작했던 도시로 돌아가는 거리 처리
        min_value = min(min_value, value + travel[next][start])
        return

    for i in range(N):
        if travel[next][i] != 0 and i != start and i not in visited:
            visited.append(i)
            dfs(start, i, value + travel[next][i], visited)
            visited.pop()


if __name__ == "__main__":

    N = int(input())
    travel = [list(map(int, input().split())) for _ in range(N)]

    # 도시의 최대 갯수는 10, 최대 거리는 1,000,000
    min_value = 10000001

    # 각 번호에서 시작
    for i in range(N):
        dfs(i, i, 0, [i])

    print(min_value)

 

 

 

세 번째 풀이

 

개인적으로는 비트 연산 자체가 자주 사용하지 않아 풀이 자체가 낯설다.
오랜만에 DP에서 주로 사용하는 메모이제이션을 활용해 풀어내는 방식을 다시 접하면서 많이 어색했는데 
실제로 작동되는 구간들을 분석해보면 훨씬 효율적으로 답을 찾아낸다. 

현재는 코드를 이해하는데도 쉽지 않아서, 이런 풀이에 익숙해지기 위한 연습이 더 필요하겠다...ㅠ

import sys


def find(now, before):
    # 남아있는 경로를 이미 방문한 적이 있음
    if dp[now][before]:
        return dp[now][before]
        # 모두 방문한 경우
    if before == (1<<n) - 1:
        return path[now][0] if path[now][0] > 0 else sys.maxsize

    # 현재 지점에서 이동할 수 있는 지점들을 탐색
    cost = sys.maxsize
    for i in range(1, n):
        # before가 다른 노드를 방문한 적이 있고, 이동하려는 지점이 이동 불가할 때
        if not (before>>i)%2 and path[now][i]:
            # i부터 0까지 순회를 만든 최소 비용
            tmp = find(i, before|(1<<i)) #before | (1<<i) == before + (1<<i) == before에 i값 십진수 변환 후 추가
            # (now~i), (i~0)의 합과 현재까지의 최소 비용과 비교
            cost = min(cost, tmp + path[now][i])

    # 메모이제이션
    dp[now][before] = cost
    return cost


n = int(sys.stdin.readline())
path = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0]*(1<<n) for _ in range(n)]

print(find(0, 1))