[ BOJ 4485 ] 녹색 옷 입은 애가 젤다지?(Python)

문제

https://www.acmicpc.net/problem/4485

문제가 웃겨서 홀린듯이.. 들어왔다.
젤다 .. 말고 링크가 동굴을 지나치면서 최소한의 금액만 잃도록 하는 문제다.
똑같은 다익스트라 문제인데, 방문 체크를 해주는 게 어려웠다.

문제 풀이

동굴의 각 칸에 있는 도둑 루피의 크기가 공백으로 구분되어 있다.
한 줄씩 입력 받으면서 공백을 제거하고,
enumerate로 인덱스와 값을 나누어서 cave[i][j] 에 도둑 루피 값을 넣어주었다.

for i in range(동굴 크기):
    row = (input().rstrip()).replace(' ','')
    for j,char in enumerate(row):
       cave[i][j]=int(char)

thief 리스트엔, 각 위치에 따라 가장 적게 잃을 수 있는 루피 값을 비교해가면서 넣어줄 것이다.

deque로 만들어준 q를 이용해 모든 위치를 방문 체크를 해나가면서 비교를 해줄 것이다.

q = deque()
q.append((0,0))
theif[0][0] = cave[0][0] 

q가 비어있지 않으면 계속 반복해준다.

 while q:
    i, j = q.popleft()
    visited[0][0]=True

    for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]
        if 0 <= nx < n and 0 <= ny < n:
            #현재 위치의 상하좌우 중 방문 안한 곳이 있으면 이동한다.
            if not visited[nx][ny]:
                # 만약 theif[이동할 좌표] 값이 
                # theif[현재 좌표] 값 + 도둑루피[이동할 좌표]의 합보다 크면
                # 더 작은 값으로 갱신해준다.
                # 그리고 q에 이동할 좌표를 넣어준다.
                if theif[nx][ny] > theif[i][j] + cave[nx][ny]:
                    theif[nx][ny] = theif[i][j] + cave[nx][ny]
                    q.append((nx,ny))

헷갈렸던 점

Q. 왜 ( i, j )에 대해서 방문체크를 안해주지?
A. ( i, j )에 대해서 방문체크를 해버리면 한번 간 곳은 두번 다시 방문할 수 없다.
그러면 최소한의 루피를 잃는 길로 가지 않고, 출구쪽으로만 이동을 하면서, 비교를 하고 이동하게 된다.

5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5

위와 같이 입력이 주어질 때, ( i, j )에 대해서 방문 체크를 한다면 theif의 값은 다음과 같다.

# 오답
[3, 10, 12, 12, 13]
[5, 13, 12, 21, 14]
[6,  8,  9, 17, 15]
[15, 16, 18, 19, 15]
[18, 22, 23, 20, 20]

# 정답
[3, 10, 11, 11, 12]
[5, 13,  9, 18, 13]
[6,  8,  9, 17, 14]
[15, 16, 18, 16, 14]
[18, 22, 22, 17, 19]

코드

import sys
from collections import deque
input = sys.stdin.readline

cnt = 0
while(1):
    #동굴 크기 n
    n = int(input().rstrip())
    cnt += 1
    if n == 0 :
        break
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    cave = [[0 for _ in range(n)] for _ in range(n)] 
    theif = [[99999 for _ in range(n)] for _ in range(n)] 
    visited = [[False for _ in range(n)] for _ in range(n)] 
    for i in range(n):
        row = (input().rstrip()).replace(' ','')
        for j,char in enumerate(row):
            if char != " ":
                cave[i][j]=int(char)

    q = deque()
    q.append((0,0))
    theif[0][0] = cave[0][0] 

    while q:
        i, j = q.popleft()
        visited[0][0]=True

        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny]:
                    if theif[nx][ny] > theif[i][j] + cave[nx][ny]:
                        theif[nx][ny] = theif[i][j] + cave[nx][ny]
                        q.append((nx,ny))
    
    print("Problem {0}: {1}".format(cnt,theif[n-1][n-1]))