[최단 경로] 백준 1261번: 알고스팟 / 골드 4

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

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

import heapq
y_lim, x_lim = map(int, input().split())

graph = []
visit = []
for i in range(x_lim):
    graph.append([x for x in input()])
    visit.append([0]*y_lim)

dx = [-1,1,0,0]
dy = [0,0,-1,1]

q = []
heapq.heappush(q, [0,0,0]) # crush,x,y

while q:
    crush, x, y = heapq.heappop(q)
    if x == x_lim-1 and y == y_lim-1: # finish
        print(crush)
        break

    if visit[x][y]==0:
        visit[x][y]=1
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<x_lim and 0<=ny<y_lim and visit[nx][ny]==0:
                if graph[nx][ny]=='1':
                    heapq.heappush(q, [crush+1,nx,ny])
                else:
                    heapq.heappush(q, [crush,nx,ny])

지도 탐색(BFS) + 최소 벽 깨기(우선순위 큐) => 다익스트라!!

아직은 최단경로 문제가 익숙하지 않아서 다익스트라에 익숙해지도록 해야겠다.