[백준] 1261 알고스팟
BFS+최단경로(다익스트라)였던 문제
입력을 문자열로 받았는데 '1'이 아닌 1로 체크해서 풀이에서 오답이 나왔었다.
import heapq
dx=[0,1,0,-1]
dy=[1,0,-1,0]
width,height=map(int,input().split())
distance=[[-1]*width for _ in range(height)]
board=[]
for i in range(height):
board.append(input())
def dijackstra(x,y):
q=[]
heapq.heappush(q,(0,x,y))
while q:
cnt,x,y=heapq.heappop(q)
distance[x][y]=0
if x==height-1 and y==width-1:
print(cnt)
return
for i in range(4):
nx=dx[i]+x
ny=dy[i]+y
if nx<0 or ny<0 or nx>=height or ny>=width:
continue
if distance[nx][ny]!=-1:
continue
if board[nx][ny]=='1':
distance[nx][ny]=distance[x][y]+1
heapq.heappush(q,(cnt+1,nx,ny))
else:
distance[nx][ny]=distance[x][y]+1
heapq.heappush(q,(cnt,nx,ny))
dijackstra(0,0)
Author And Source
이 문제에 관하여([백준] 1261 알고스팟), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@code12/백준-1261-알고스팟저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)