[Algorithm🧬] 코딩 인터뷰 완전 분석 : 자외선을 피해 가기

문제 설명

영희는 자외선이 피부에 좋지 않기 때문에 이동 시 자외선에 노출되는 것을 최소한으로 하고 싶어서 가는 길의 자외선 양을 모두 조사하였다.
값이 제 각각이어서 어떤 경로로 가야 좋을지 난감한 영희를 도와주자.
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)] 이렇게 해야 한다고 한다....... 충격

https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly