[테스트케이스 추가] 백준 1261번: 알고스팟 (python, 파이썬)

1. 문제

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

1261번: 알고스팟

 

 

 

2. 풀이

1) input을 받을 때 split()을 하지 못하는 것과 readline을 하면 줄바꿈('\n')이 함께 들어온다는 것을 명심해야한다.

2) N과 M은 둘이 서로 다른 예시를 넣어서 index 에러로 빠르게 확인한다.

 

 

 

3. 구현

import sys
import heapq
import math

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

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

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

M,N=map(int, sys.stdin.readline().split())
lis=[]
for i in range(N):
    num = sys.stdin.readline()
    tmp=[]
    for j in range(len(num)):
      if num[j]=='\n':
        continue
      tmp.append(int(num[j]))
    lis.append(tmp)
# print(lis)

dist=[[math.inf for _ in range(M)] for __ in range(N)]
edges=[]

dist[0][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,M):
      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(dist)
print(dist[N-1][M-1])

 

 

 

4. 추가 테스트케이스

4 10
1111
0100
0100
1100
1011
1010
1000
0101
1011
0010

답 4