[백준] 10971번

그녕·2023년 3월 14일
0

알고리즘 문제 풀이

목록 보기
14/29

백준 10971번

😢😢😢😢잘 모르겠다... 다음에 다시 풀어볼 것...😢😢😢😢

DFS

💗내 풀이💗

이 문제는 오랜시간동안 봤는데도 좀 이해가 덜 되는 문제이다.
코드 1번이 좀 더 이해가 잘 되는거 같아서 1번으로 설명을 해보겠다. min_value를 출력할 최솟값으로 정의를 해준다.
dfs 함수에서는 도시의 개수만큼 for문을 돌려서 갈수 있는 길(0이 아닐경우)이면서 방문을 안했고 이때까지 계산한 최소값보다 value가 적으면 visited에 그 도시를 추가해준다. 다시 dfs를 해주고 visited.pop을 해준다.(이때 pop을 왜 하는지 모르겠다)

그리고 마지막 도시에서 출발도시로 가는 비용이 0이 아닐경우(즉 갈수 있다면) minvalue와 이번에 구한 값과 비교 했을때 더 적은 애를 minvalue에 넣는다.

그 다음 main에서는 출발점을 0,1,2,3 이렇게 4번해서 다 돌아준다.
dfs(i, i, 0, [i])으로 해주고 min_value를 출력해준다.

💗내 코드 1💗

import sys
N = int(input())
travel_cost = [list(map(int, input().split())) for _ in range(N)]
min_value = sys.maxsize

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

    if len(visited) == N:
        if travel_cost[next][start] != 0:
            min_value = min(min_value, value + travel_cost[next][start]) 
            return
 
    for i in range(N):
        if travel_cost[next][i] != 0 and i not in visited and value < min_value: 
            visited.append(i)
            dfs(start, i, value + travel_cost[next][i], visited)
            visited.pop() #왱??

for i in range(N):
    dfs(i, i, 0, [i])
print(min_value)

💗내 코드 2💗

N= int(input())
maps=[]
for _ in range(N):
    maps.append(list(map(int,input().split())))
visited= [0]*N
tmp=1000000
add=0

def dfs(i,add,visited):
    global tmp
    if add> tmp:
        return
    if sum(visited)==N-1:
        if maps[i][0]:
            tmp=min(tmp,add+maps[i][0])
            return
    for j in range(1,N):
        if maps[i][j] and visited[j]==0:
            visited[j]=1
            dfs(j,add+maps[i][j],visited)
            visited[j]=0
            
            
for i in range(1,N):
    if maps[0][i]:
        visited[i]=1
        dfs(i,add+maps[0][i],visited)
        visited[i]=0 #why???
print(tmp)

0개의 댓글