[SWEA 5265][Python][파이썬 S/W 문제해결 최적화] 4일차 - 전기카트2(D4) (백준 2098)

코드1 :  DFS 백트랙킹(시작점이 고정이 아닐 경우 시간초과 가능성 있음)

## SWEA 5365 : 순회외판원문제 : dfs백트랙킹 풀이 -- 시간초과 가능성 있음
def dfs(now,value,cnt):
    global result
    if cnt == N:
        if arry[now][0] != 0 :
            value += arry[now][0]
            if result > value:
                result = value

    if value > result:
        return

    for next in range(1,N):
        if visited[next] == 0 and arry[now][next] != 0 :
            visited[next] = 1
            dfs(next, value + arry[now][next], cnt + 1)
            visited[next] = 0

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arry = [list(map(int, input().split())) for _ in range(N)]
    result = float("inf")
    visited = [0]*N
    dfs(0,0,1)

    print(f"#{test_case} {result}")

풀이1

처음에는 완전탐색(DFS 백트랙킹)으로 접근하여 풀었다.

하지만 DP 실습 단원이었기 때문에 DP를 적용해서 다르게 풀어보기로 했다.

 

 

코드2 : DFS + DP + 비트연산자 

## SWEA 5365 : 순회외판원문제 : dfs+dp+비트연산
def dfs(now,visited):
    if visited == visited_all :
        return arry[now][0]

    if dist_arry[now][visited] != None :
        return dist_arry[now][visited]

    tmp = INF
    for next in range(N):
        if visited & (1<<next) == 0 and dist_arry[now][next] != 0 :
            tmp = min( tmp, dfs(next, visited|(1<<next)) + arry[now][next] )
    dist_arry[now][visited] = tmp
    return tmp

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arry = [list(map(int, input().split())) for _ in range(N)]
    dist_arry = [[None]*(1<<N) for _ in range(N)]
    INF = float("inf")
    visited_all = (1<<N)-1
    result = dfs(0, 1<<0)
    print(f"#{test_case} {result}")

풀이2

DP 활용법 감을 못잡아서 구글링 해보니 이 문제는 백준2098 외판원순회 문제와 비슷한 SWEA 버전 문제였다.

(본 문제는 시작 지점이 고정되어 백트래킹으로 풀린 듯 하다.) 

원래라면 DP+DFS+비트연산자 까지 써서 해결이 되는 문제였다.

그동안 비트연산자가 익숙하지 않아 최대한 visited list를 생성하여 대체하고자 했지만,

이 문제에선 비트연산자가 다음 방문 노드를 결정하는 핵심 개념인 것 같아 공부했다. 

그리고 백트래킹과 DP는 비슷한 개념인 것 같은데.. 

이번 문제는 DP와 백트래킹 개념의 교집합? 정도의 문제인 것 같다. 

DP를 왜 써야하는지.. 비트연산자를 왜 쓰는지 좀 더 깊게 생각해보면 실력 향상에 도움이 될 것 같아 추후 공부하여 포스팅 하도록 하겠다.