[BOJ / Python] 4485번 : 녹색 옷 입은 애가 젤다지?

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

4485번: 녹색 옷 입은 애가 젤다지?

 

문제

 

풀이

최솟값을 출력해야 하므로 BFS방식을 사용하되 이 문제에서는 힙큐(heapq)로 가중치가 작은 위치가 먼저 pop되도록 한다.

가장 위쪽의 표는 문제의 예시들 중 하나고, 아래의 표들은 순차적으로 가중치값을 구하는 과정이다. 첫번째 표는 (0,0)위치에서 시작하기 때문에 왼쪽 상단에 5를 먼저 넣어두고, 해당 칸과 밀접하게 붙어있는 칸들의 값에 5을 각각 더해서 두번째 표를 만들어낸다. 세번째 표에서는 새로 생긴 8, 10 중에서 가장 작은 값은 8이므로 8에 밀접하며 비어있는 칸들에 대해 해당 칸의 값과 8을 더해 그 칸에 넣어준다. 마찬가지로 네번째 표는 10, 11, 17 중에서 10의 크기가 가장 작기 때문에 10에 밀접한 칸을 같은 방식으로 채워주고, 다섯번째 칸도 11, 14, 17 중 가장 작은 값인 11에 대해 밀접한 칸의 값들을 채워준다. 여섯번째 칸에서는 가장 오른쪽 하단에 값이 들어가게 되는데, 이 문제에서 구하고자 하는 칸이 가장 오른쪽 하단이었으므로 모든 칸의 값을 채우지 않았음에도 불구하고 코드를 종료시킨 뒤 결과를 출력해내는 방식을 사용한다.

문제의 수는 여러개가 될 수 있기 때문에 해당 문제의 결과를 저장할 result라는 리스트를 만들어 두고, dx와 dy의 값도 미리 설정해둔다. while True 내에서 n에는 표의 길이를 입력하는데, 만약 n이 0이라면 break를 이용해 while문을 나오도록 한다. 가중치값을 저장할 visit 리스트를 표의 크기와 같게 생성하는데, 이때 visit 값들은 모두 -1로 통일시켜둔다. 그리고 표의 내용은 data 리스트에 저장하도록 한다. 시작 지점인 visit[0][0]의 값은 0을 넣고, 힙큐인 q를 생성한 뒤 q에 [가중치, x, y] 순으로 값을 넣는다. q에 값이 들어있지 않을 때까지 while문으로 반복하는데, q의 왼쪽에서 값을 pop하는 동시에 d, x, y에 가중치, x, y값들을 저장시킨다. 그리고 위에서 만들어둔 dx, dy 리스트를 하나씩 사용하며 해당 칸에 밀접하는 동시에 visit[nx][ny]의 값이 -1이라면 여기에 d+1의 값을 넣고, [d+1, nx, ny]를 q에 넣는다. 코드가 돌아가는 시간을 단축시킬 수 있도록 while문 안에 visit[n-1][n-1]의 값이 -1인지 아닌지를 반복적으로 확인하고, 만약 -1이 아니라면 break로 반복문을 빠져나와 visit[n-1][n-1]을 결과값으로 result 리스트에 저장한다. 마지막으로 모든 반복문이 끝이 난다면, 정해진 양식에 맞추어 result의 값을 하나씩 출력해낸다. 이를 코드로 나타내면 아래와 같다. 

 

코드

from heapq import *
input=__import__('sys').stdin.readline
result=[]
dx,dy=[-1,1,0,0],[0,0,-1,1]
while True:
  n=int(input())
  if n==0:
    break
  visit=[[-1]*n for _ in range(n)]
  data=[]
  for i in range(n):
    data.append([*map(int,input().split())])
  q=[]
  visit[0][0]=data[0][0]
  heappush(q,[visit[0][0],0,0])
  while q:
    d,x,y=heappop(q)
    for k in range(4):
      nx,ny=x+dx[k],y+dy[k]
      if 0<=nx<n and 0<=ny<n and visit[nx][ny]==-1:
        visit[nx][ny]=visit[x][y]+data[nx][ny]
        heappush(q,[visit[nx][ny],nx,ny])
    if visit[n-1][n-1]!=-1:
      result.append(visit[n-1][n-1])
      break
for i in range(len(result)):
  print("Problem {}: {}".format(i+1, result[i]))

 

결과