영희는 자외선이 피부에 좋지 않기 때문에 이동 시 자외선에 노출되는 것을 최소한으로 하고 싶어서 가는 길의 자외선 양을 모두 조사하였다.
값이 제 각각이어서 어떤 경로로 가야 좋을지 난감한 영희를 도와주자.
N*N 모양의 장소의 모든 길의 자외선 양이 주어지고 영희는 상하좌우 한 칸씩만 이동이 가능하다.
시작점(1,1)에서 도착점(N,N)까지 이동 시 자외선 합의 최소값을 찾아라.
예를 들어 3*3 장소의 자외선 양이 아래와 같다면 오른쪽처럼 이동하면 8만큼만 노출된다.
첫 줄에 N(2≤N≤100)이 들어온다.
그 다음 줄부터 N개의 줄에 각각 N개씩 M(0≤M≤9)이 공백 없이 들어온다.
3
041
253
620
출발점에서 도착점까지 자외선 합의 최소값을 출력한다.
8
import sys
from collections import deque
def BFS():
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
q = deque()
q.append((0, 0, sun_map[0][0]))
min_sun_map[0][0] = sun_map[0][0]
while q:
r, c, sun = q.popleft()
# 여기서는 BFS 가 무조건 작은 것을 선택하면서 가는게 아니라 모든 경로에 대해 탐색해보고 가장 작은 값을 선택해야해서 종료 조건은 안걸어주는 것이 맞다.
# if r == N - 1 and c == N - 1:
# return sun
for x, y in moves:
tr, tc = r + x, c + y
if not 0 <= tr < N:
continue
if not 0 <= tc < N:
continue
tsun = sun + sun_map[tr][tc]
if min_sun_map[tr][tc] <= tsun:
continue
min_sun_map[tr][tc] = tsun
q.append((tr, tc, tsun))
return -1
N = int(sys.stdin.readline())
sun_map = []
for i in range(N):
l = []
for c in sys.stdin.readline()[:-1]:
l += [int(c)]
sun_map += [l]
# min_sun_map = [[999999] * N] * N
min_sun_map = [[999999] * N for _ in range(N)]
BFS()
print(min_sun_map[N - 1][N - 1])
처음에 이렇게 풀었는데 min_sun_map[0][0] = sun_map[0][0]
여기서 모든 행의 0번째 element 가 바뀌어서... 의아했는데 min_sun_map = [[999999] * N] * N
가 아니라 min_sun_map = [[999999] * N for _ in range(N)]
이렇게 해야 한다고 한다....... 충격