[테스트케이스 추가] 백준 4485번 녹색 옷 입은 애가 젤다지? (python, 파이썬)

1. 문제

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

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

2. 풀이

주어진 지도가 graph라고 생각하고 dist도 같은 모양으로 만들어서

상하좌우를 순회한다.

 

3. 구현

import sys
import heapq
import math

sys.stdin=open('input.txt')

dr = [0,1,0,-1]
dc = [1,0,-1,0]

def valid(r,c,len):
  return r>=0 and c>=0 and r<len and c<len

t=0
while True:
  t+=1
  n=int(sys.stdin.readline())
  if n==0:
    break
  cnt=n
  lis=[]
  while cnt:  
    lis.append(list(map(int, sys.stdin.readline().split())))
    cnt-=1
  
  dist=[[math.inf for _ in range(n)] for __ in range(n)]
  edges=[]

  dist[0][0]=lis[0][0]
  heapq.heappush(edges, (dist[0][0],0,0))

  while edges:
    weight,curR,curC = heapq.heappop(edges)
    for idx in range(4):
      nextR = curR+dr[idx]
      nextC = curC+dc[idx]
      if not valid(nextR,nextC,n):
        continue
      if dist[nextR][nextC]>dist[curR][curC]+lis[nextR][nextC]:
        dist[nextR][nextC]=dist[curR][curC]+lis[nextR][nextC]
        heapq.heappush(edges, (dist[nextR][nextC],nextR,nextC))

  print(f"Problem {t}: {dist[n-1][n-1]}")

4. 테스트케이스 추가

2
5 1
3 5
3
0 8 4
9 1 9
2 1 6
8
6 5 3 7 8 8 7 5
8 0 9 0 9 0 4 2
9 6 6 4 5 0 6 8
7 6 1 4 2 2 9 5
3 3 4 7 7 4 6 9
6 9 1 2 1 7 7 1
7 9 7 8 2 8 8 4
1 1 7 1 3 1 8 5
12
3 8 8 2 0 3 8 4 4 6 7 5
0 6 3 9 6 4 2 0 0 2 7 2
8 1 8 5 2 1 0 0 0 0 9 2
7 8 0 8 5 4 6 4 3 6 4 3
7 8 8 4 7 8 1 0 1 8 2 2
2 4 1 7 8 6 3 8 9 3 2 1
6 1 7 9 5 8 2 7 4 4 6 9
0 0 2 2 1 4 0 7 1 9 7 8
2 7 0 8 4 5 7 5 4 7 7 0
2 8 4 9 8 5 2 3 5 4 5 9
7 2 9 8 8 5 2 7 4 3 8 6
5 6 9 5 4 7 2 6 8 5 6 4
17
2 5 7 7 6 0 4 0 6 0 9 8 9 8 3 4 7
6 3 5 9 5 1 3 7 5 3 3 1 3 4 1 9 3
4 1 3 8 5 9 9 7 7 6 4 5 8 8 4 3 1
2 8 2 1 5 0 1 2 8 7 8 1 3 9 8 5 3
5 2 1 7 7 5 7 6 6 5 0 3 5 0 3 2 9
6 1 2 3 7 2 0 9 7 6 3 3 3 3 3 7 2
3 8 2 7 6 6 5 2 4 9 3 6 3 3 0 5 5
9 2 4 7 5 1 2 3 7 1 2 4 1 9 9 1 6
2 1 3 1 4 5 5 7 5 2 9 7 2 5 1 0 6
2 8 4 6 3 7 6 6 1 7 8 6 4 0 1 9 6
6 3 3 3 2 7 7 2 3 0 4 5 7 6 7 3 4
2 2 3 9 5 9 5 2 6 1 9 2 4 3 8 1 8
3 7 3 6 6 8 8 8 3 5 5 4 8 6 8 9 3
3 5 8 1 3 0 8 6 8 3 9 4 0 9 1 3 0
0 2 2 3 7 8 9 3 3 6 3 2 4 0 6 8 5
7 2 9 7 4 0 1 0 6 5 8 6 2 3 6 4 3
2 2 1 7 7 0 9 7 5 2 4 5 7 8 1 9 5
24
7 1 6 8 5 5 3 9 1 4 8 0 8 2 5 2 8 7 8 8 1 1 3 1
8 6 6 2 1 0 8 5 3 2 8 0 5 8 0 4 8 4 1 6 7 2 1 3
5 7 1 0 0 9 6 6 3 0 3 9 5 0 3 0 0 3 1 4 8 9 4 4
0 1 0 2 9 1 4 1 6 1 7 3 5 2 5 2 3 6 4 4 8 9 5 1
5 7 3 2 3 9 4 9 0 5 0 6 9 5 9 3 7 7 3 9 7 1 6 3
1 4 5 8 7 7 0 1 7 1 1 6 9 8 1 9 0 7 0 8 3 4 3 4
4 1 6 7 9 8 7 7 2 3 9 7 5 0 6 6 9 5 4 4 4 2 8 0
4 9 3 7 2 9 5 2 3 7 6 4 6 3 7 9 2 7 2 3 2 3 7 7
0 1 8 9 9 5 1 7 3 2 9 3 1 4 6 0 1 8 7 8 7 0 7 0
5 1 6 7 9 6 3 3 7 9 3 4 5 3 2 8 5 2 6 4 2 7 8 7
4 4 2 5 9 9 6 9 6 3 5 5 2 3 7 4 5 4 7 2 8 5 7 0
4 6 8 1 4 3 4 1 5 4 4 4 6 1 3 1 4 1 1 4 3 8 6 0
7 7 7 6 8 2 4 6 4 3 5 4 1 1 3 0 3 0 1 3 5 2 6 9
2 1 7 9 3 6 1 7 4 4 5 2 1 4 4 3 6 5 2 6 2 2 9 8
8 1 9 6 2 6 3 9 7 9 7 8 5 2 5 8 0 0 1 1 5 4 6 3
9 8 4 5 4 7 7 6 9 6 4 8 7 9 3 5 6 3 1 8 1 3 4 3
5 6 2 9 6 6 1 7 8 3 5 2 6 5 9 1 8 4 8 4 2 7 9 5
7 2 5 2 8 4 4 2 5 3 3 4 2 6 4 3 2 3 2 4 7 3 2 9
7 4 2 0 7 4 8 6 2 4 3 3 9 5 3 4 6 4 9 2 1 1 3 9
8 2 0 0 7 1 7 4 3 0 2 7 2 5 8 7 5 7 3 0 0 0 6 1
8 4 9 8 0 0 2 1 8 8 3 2 7 6 6 3 4 7 9 4 8 4 9 3
9 4 9 0 2 7 2 2 4 1 3 4 7 2 0 8 9 3 2 9 2 0 0 4
0 0 0 4 5 2 1 4 2 3 5 3 6 4 5 6 2 4 0 4 1 1 9 1
1 7 3 2 1 3 6 7 6 3 1 6 1 9 5 1 4 7 5 0 0 1 2 3
0

답

Problem 1: 11
Problem 2: 16
Problem 3: 51
Problem 4: 75
Problem 5: 96
Problem 6: 118