개발공부/[코딩테스트_SWEA]
[SWEA 1247][Python][S/W 문제해결 응용] 3일차 - 최적 경로
왜지?
2022. 12. 30. 09:10
반응형
코드
## SWEA 1247
def dfs(node,dist):
global result
if dist > result:
return
if sum(visited) == len(visited) :
tmp = abs(node_arry[node][0]-end[0])+abs(node_arry[node][1]-end[1])
dist += tmp
if dist < result :
result = dist
return
for i in range(N):
if visited[i] == 0 :
visited[i] = 1
tmp = abs(node_arry[node][0] - node_arry[i][0])+abs(node_arry[node][1] - node_arry[i][1])
dist += tmp
dfs(i,dist)
dist -= tmp
visited[i] = 0
T = int(input())
for test_case in range(1, T + 1):
N = int(input())
arry = list( map(int, input().split()) )
start = [arry[0],arry[1]]
end = [arry[2], arry[3]]
node_arry = []
for i in range(4, len(arry), 2) :
node_arry.append( [arry[i],arry[i+1]] )
result = float("inf")
for i in range(N):
visited = [0] * N
visited[i] = 1
dist = abs(start[0]-node_arry[i][0])+abs(start[1] - node_arry[i][1])
dfs(i,dist)
print(f"#{test_case} {result}")
풀이
문제에서 완전탐색으로 풀라고 가이드를 줘서 DFS로 풀었다.
반응형