[미로 탈출] DFS&BFS | 이것이 코딩이다 | python

유튜브로 "이것이 코딩이다" DFS&BFS 문제를 풀어보다 "미로 탈출" 문제에서 오류가 발생했다.

👾 문제

 

📍 풀이

입력

3 3
110
010
011

5 6
101010
111111
000001
111111
111111

• 인접한 노드에 자신의 노드 값을 +1 함

 

⚒️ 코드

from collections import deque

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

graph = [] * n # 잘못된 부분 ㅠ
for _ in range(n):
    graph.append(list(map(int, input().split())))

result = 0

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


def bfs(x, y):
    myqueue = deque()
    myqueue.append((x, y))

    while myqueue:
        x, y = myqueue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]


            if 0 <= nx < n and 0 <= ny < m:  # 범위 확인
                if graph[nx][ny] == 0: # 괴물
                    continue

                if graph[nx][ny] == 1: # 지나갈 길
                    graph[nx][ny] = graph[x][y] + 1 # 인접 노드에 +1
                    myqueue.append((nx, ny))

    return graph[n - 1][m - 1]


print(bfs(0, 0))

 

😓 오류

if 0 <= nx < n and 0 <= ny < m:  # 범위 확인
                if graph[nx][ny] == 0:
                    continue

이 부분에서 오류가 났다.
범위 확인을 한 뒤에 graph[nx][ny]를 했는데, list index out of range라고...

처음엔 조건문을 잘못 썼나 싶었지만 graph 배열을 잘못 담았다.

😄 해결

graph = [] * n
for _ in range(n):
   graph.append(list(map(int, input().split())))

# print(graph)
# [[101010], [111111], [1], [111111], [111111]]

이 부분에서 원하는 대로 배열이 안담겨졌다.

왜그럴까.

graph를 선언할 때 [] 빈 배열을 n번 곱해서 그렇다..!

graph = []

graph는 빈 배열로 선언하고, 각 줄에서 입력받은 숫자들을 개별 숫자로 분리하여 리스트에 추가했더니 해결됐다!

graph = []
for i in range(n):
    graph.append(list(map(int, input())))

 

[[1, 0, 1, 0, 1, 0], [1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]

잘 담겨진다.