[백준] 1261번(알고스팟)

백준 1261번

최종 제출 코드

from collections import deque

m, n = map(int,input().split())
queue = deque()
array = [input() for _ in range(n)]
visited = [[m*n for _ in range(m)] for _ in range(n)]

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

def bfs():
  
  queue.append([0,0])
  visited[0][0] = 0

  while queue:

    x, y = queue.popleft()

    for i in range(4):
      if x+dx[i] < 0 or x+dx[i] >= m or y+dy[i] < 0 or y+dy[i] >= n:
        continue
      if visited[y+dy[i]][x+dx[i]] != m*n:
        continue
 
      if array[y+dy[i]][x+dx[i]] == "1":
        visited[y+dy[i]][x+dx[i]] = visited[y][x] + 1
        queue.append([x+dx[i], y+dy[i]])
      else:
        visited[y+dy[i]][x+dx[i]] = visited[y][x]
        queue.appendleft([x+dx[i], y+dy[i]])

  return visited[n-1][m-1]

print(bfs())

◼ array의 원소값이 0인 인덱스에 우선 접근

• 이 순서를 고려해주지 않으면 경우에 따라 최소값을 구할 수 없음
  ⇒ array[i][j]가 0이면 appendleft, 1이면 append