-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path5250_최소비용.py
149 lines (112 loc) · 4.25 KB
/
5250_최소비용.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# 다익스트라 알고리즘 적용 문제
# 이 방법으로 풀면 시간 초과
# test_num = int(input())
# D = [(0,1), (0,-1), (1,0), (-1,0)]
# for t in range(test_num):
# N = int(input())
# min_result = 999999
# board = [0] * N
# for i in range(N):
# board[i] = list(map(int,input().split()))
# def findWay(i,j,cost,visited):
# global min_result
# if i == N-1 and j == N-1:
# if cost < min_result:
# min_result = cost
# return
# if cost >= min_result:
# return
# else:
# temp_vis = [0] * N
# for a in range(N):
# temp_vis[a] = visited[a][:]
# temp_vis[i][j] = True
# for a in range(4):
# di, dj = D[a]
# ri = i + di
# rj = j + dj
# # print(ri,rj)
# if 0 <= ri < N and 0 <= rj < N:
# if not temp_vis[ri][rj]:
# temp = 0
# if board[ri][rj] > board[i][j]:
# temp = board[ri][rj] - board[i][j]
# findWay(ri, rj, cost + 1 + temp, temp_vis)
# findWay(0,0,0,[[False for j in range(N)] for i in range(N)])
# print('#' + str(t+1) + ' ', end='')
# print(min_result)
# 다익스트라 적용 - 아직도 느림()
# from pprint import pprint
# test_num = int(input())
# D = [(0,1), (0,-1), (1,0), (-1,0)]
# for t in range(test_num):
# N = int(input())
# min_result = 999999
# board = [0] * N
# for i in range(N):
# board[i] = list(map(int,input().split()))
# processed = [[False for j in range(N)] for i in range(N)]
# distance = [[99999999 for j in range(N)] for i in range(N)]
# distance[0][0] = 0
# while True:
# # pprint(distance)
# current_i = -1
# current_j = -1
# min_dist = 99999999
# if processed[N-1][N-1]:
# break
# for i in range(N):
# for j in range(N):
# if (processed[i][j] == False) and distance[i][j] < min_dist:
# current_i = i
# current_j = j
# min_dist = distance[i][j]
# # print(current_i, current_j)
# processed[current_i][current_j] = True
# for i in range(4):
# di, dj = D[i]
# ri = current_i + di
# rj = current_j + dj
# if 0 <= ri < N and 0 <= rj < N:
# temp = 0
# if board[ri][rj] > board[current_i][current_j]:
# temp = board[ri][rj] - board[current_i][current_j]
# if not processed[ri][rj] and distance[ri][rj] > min_dist + 1 + temp:
# distance[ri][rj] = min_dist + 1 + temp
# print('#' + str(t+1) + ' ', end='')
# print(distance[N-1][N-1])
# 힙큐 사용한 다익스트라 적용
from pprint import pprint
from heapq import heappop, heappush
test_num = int(input())
D = [(0,1), (0,-1), (1,0), (-1,0)]
for t in range(test_num):
N = int(input())
board = [0] * N
queue = []
for i in range(N):
board[i] = list(map(int,input().split()))
distance = [[99999999 for j in range(N)] for i in range(N)]
distance[0][0] = 0
heappush(queue,(0,0,0))
while queue:
current_dist, current_i, current_j = heappop(queue)
# print(current_dist, current_i, current_j)
if current_dist > distance[current_i][current_j]: # 여기 다시보기
continue
for i in range(4):
di, dj = D[i]
ri = current_i + di
rj = current_j + dj
if 0 <= ri < N and 0 <= rj < N:
temp = current_dist + 1
if board[ri][rj] > board[current_i][current_j]:
temp = current_dist + 1 + (board[ri][rj] - board[current_i][current_j])
if distance[ri][rj] > temp:
distance[ri][rj] = temp
heappush(queue, (temp, ri, rj))
if current_i == N-1 and current_j == N-1:
break
# print(distance)
print('#' + str(t+1) + ' ', end='')
print(distance[N-1][N-1])