백준 1261 파이썬 : 알고스팟

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

1261번: 알고스팟

 

< 설명 >

해당 위치의 방문 여부와 벽 부순 횟수를 보관하는 배열이 추가적으로 필요했다.

이 문제 포인트는 큐에 벽과 빈방을 구분해 삽입하는 거다. BFS 에서 popleft 로 현재의 위치(x,y)를 얻는다고 했을 때,

현 위치에서의 네 방향 중 벽은 q.append 를, 빈방은 q.appendleft 를 통해 빈방이 우선적으로 pop 되도록 작성한다.

이 때 빈 방의 경우 벽을 부수지 않았으므로 현 위치의 부순 횟수가 그대로, 벽은 +1 되어 갱신된다.

 

< 소스 코드 >

from collections import deque
# 가로크기 M 세로 크기 N

m,n = map(int,input().split())
data = []

for _ in range(n):
  data.append(list(input()))
  
# 방문 여부와 그 위치까지 벽 부순 횟수 보관 리스트
visited = [[-1]*m for _ in range(n)] 
# 시작점은 방문 완료 표시
visited[0][0] = 0
q = deque()
q.append((0,0))

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

def bfs():
  
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 범위 체크
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      # 방문 x && 빈 방
      if data[nx][ny] == '0' and visited[nx][ny] == -1:
        q.appendleft((nx,ny))
        visited[nx][ny] = visited[x][y]
      # 방문 x && 벽
      if data[nx][ny] == '1' and visited[nx][ny] == -1:
        q.append((nx,ny))
        visited[nx][ny] = visited[x][y] + 1
      
bfs()
print(visited[n-1][m-1])