[백준] 2178번: 미로 탐색

📌 알고리즘 정리

---

📃 문제

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

2178번: 미로 탐색

---

✍ 풀이과정

최단 경로를 구하는 문제이므로 bfs를 통해 문제를 해결함

'1743번: 음식물 쓰레기' 문제를 먼저 풀었는데 다시 돌아와서 문제를 보니 비슷하게 풀면 되겠다는 생각이 들었다.

import sys
from collections import deque

n, m = map(int, input().split())

board=[]
visited =[[0]*m for _ in range(n)]
for _ in range(n):
    board.append(list(input()))

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

# 시작점
queue = deque()
visited[0][0] = 1
queue.append((0, 0))

while queue:
    cur_x, cur_y = queue.popleft()
    if cur_x == n-1 and cur_y == m-1:
        print(visited[cur_x][cur_y])
        break

    for i in range(4):
        X = cur_x + dx[i]
        Y = cur_y + dy[i]

        if 0 <= X < n and 0 <= Y < m and visited[X][Y] == 0 and board[X][Y] == '1':
            queue.append((X, Y))
            visited[X][Y] = visited[cur_x][cur_y] + 1

 

1743번과 다르게 visited 리스트에 지나온 칸 수를 저장하였다.

---

Deque 초기화 Error

# 오류 1
queue = deque((0, 0))
visited[0][0] = 1

# 오류 2
queue = deque([0, 0])
## deque([0, 0])

# 올바른 코드 1
queue = deque()
visited[0][0] = 1
queue.append((0, 0))

# 올바른 코드 2
queue = deque([(0, 0)])
## deque([(0, 0)])

while queue:
    cur_x, cur_y = queue.popleft()
    if cur_x == n-1 and cur_y == m-1:
        print(visited[cur_x][cur_y])
        break

TypeError: 'int' object is not iterable

 

시작점을 deque에 넣는 코드를 (오류 1), (오류 2) 처럼 작성했더니 TypeError가 발생하였다.

deque 내에 tuple이나 list로 초기화를 하게 되면 deque([0, 0]) 처럼 하나의 리스트가 생성되므로

while 문 내에서 cur_x는 0을 할당받고, cur_y는 할당받는 것이 없어서 에러가 발생한 것이다.

 

popleft로 x, y를 얻고 싶다면,

1) append 사용

2) [( )] 사용

 

 

https://trey-de.tistory.com/14

Python에서 deque.popleft() 실행 시, iterable error가 뜬다면?