[백준]1261 알고스팟 파이썬 python

문제링크

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

1261번: 알고스팟

코드

import sys
from collections import deque
 
input = sys.stdin.readline
#입력
m,n = map(int, input().split())
map = [ list(map(int,input().rstrip())) for _ in range(n)]
visited = [[-1]*m for _ in range(n)]
dx = [0,0,-1,1]
dy = [1,-1,0,0]
 
def bfs():
    q = deque()
    q.append((0,0))
    visited[0][0] = 0
    while q:
        x,y = q.popleft()
        if x==n-1 and y==m-1: #도착
            return visited[x][y]
 
        for i in range(4): #상하좌우 움직이기
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny]==-1:
                if map[nx][ny] == 0: #방(가중치0)
                    visited[nx][ny] = visited[x][y]
                   q.appendleft((nx,ny))#우선순위 get
                else: #벽(가중치1)
                    visited[nx][ny] = visited[x][y]+1
                    q.append((nx, ny))
print(bfs())
 
 

Point

1) 가중치가 다른 최단 경로 찾기로 접근할 수 있다. --> deque을 사용해 BFS로 접근

노드 : 미로의 각 좌표

간선 : 행동 2개(방으로 이동, 벽으로 이동)

벽을 부수는 횟수가 최소가 되야하기에,

방으로 이동하는 경우(-> 가중치0) vs 벽을 부수는 경우(->가중치1) 로 정의할 수 있다.

방을 이동하는 경우에 우선순위를 부여하기위해, 코드상에서 deque.appendleft()를 사용하였고 벽을 방문하는 경우보다 앞에 배치하였다.