[BOJ] 백준 2178번 - 미로 탐색 (Python)

문제

문제 바로가기

해결

from collections import deque

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

# 동, 남, 서, 북
move_m = [1,0,-1,0]
move_n = [0,1,0,-1]

q = deque()
x = y = cnt = 0

q.append((x, y))
         
while q:
  x, y = q.popleft()
  print("y, x =", y, x)
  for i in range(4):
    nx = x + move_m[i]
    ny = y + move_n[i]
    print("ny, nx =", ny, nx)
  
    if nx < 0 or ny < 0 or nx >= m or ny >= n:
      continue
    if graph[ny][nx] == 0:
      continue
    if graph[ny][nx] == 1:
      graph[ny][nx] = graph[y][x] + 1
      q.append((nx, ny))
    
print(graph[n-1][m-1])

입출력

4 6
101111
101010
101011
111011
y, x = 0 0
ny, nx = 0 1
ny, nx = 1 0
ny, nx = 0 -1
ny, nx = -1 0
y, x = 1 0
ny, nx = 1 1
ny, nx = 2 0
ny, nx = 1 -1
ny, nx = 0 0
y, x = 2 0
ny, nx = 2 1
ny, nx = 3 0
ny, nx = 2 -1
ny, nx = 1 0
y, x = 0 0
ny, nx = 0 1
ny, nx = 1 0
ny, nx = 0 -1
ny, nx = -1 0
y, x = 3 0
ny, nx = 3 1
ny, nx = 4 0
ny, nx = 3 -1
ny, nx = 2 0
y, x = 3 1
ny, nx = 3 2
ny, nx = 4 1
ny, nx = 3 0
ny, nx = 2 1
y, x = 3 2
ny, nx = 3 3
ny, nx = 4 2
ny, nx = 3 1
ny, nx = 2 2
y, x = 2 2
ny, nx = 2 3
ny, nx = 3 2
ny, nx = 2 1
ny, nx = 1 2
y, x = 1 2
ny, nx = 1 3
ny, nx = 2 2
ny, nx = 1 1
ny, nx = 0 2
y, x = 0 2
ny, nx = 0 3
ny, nx = 1 2
ny, nx = 0 1
ny, nx = -1 2
y, x = 0 3
ny, nx = 0 4
ny, nx = 1 3
ny, nx = 0 2
ny, nx = -1 3
y, x = 0 4
ny, nx = 0 5
ny, nx = 1 4
ny, nx = 0 3
ny, nx = -1 4
y, x = 0 5
ny, nx = 0 6
ny, nx = 1 5
ny, nx = 0 4
ny, nx = -1 5
y, x = 1 4
ny, nx = 1 5
ny, nx = 2 4
ny, nx = 1 3
ny, nx = 0 4
y, x = 2 4
ny, nx = 2 5
ny, nx = 3 4
ny, nx = 2 3
ny, nx = 1 4
y, x = 2 5
ny, nx = 2 6
ny, nx = 3 5
ny, nx = 2 4
ny, nx = 1 5
y, x = 3 4
ny, nx = 3 5
ny, nx = 4 4
ny, nx = 3 3
ny, nx = 2 4
y, x = 3 5
ny, nx = 3 6
ny, nx = 4 5
ny, nx = 3 4
ny, nx = 2 5
15

고찰

풀이 과정 자체는 정답과 비슷하게 작성을 하였으나, 첫 번째, 두 번째 시도 모두에서 각각 시간 초과와 메모리 초과가 발생하였다. 당시 코드에서는 cnt 변수를 따로 설정하여 경로를 하나씩 처리해 주었다. 혹은 x, y와 함께 큐에 삽입해주고 popleft()을 해주어서 막다른 골목일 경우 이전 x,y와 함께 cnt까지 불러오도록 하였다. 하지만 그것보다 훨씬 간단한 방법이 있었다.

바로 그래프에 직접적으로 경로를 작성해 나가는 것이었는데, 그렇게 되면 지나온 경로를 0으로 수정할 수 없기 때문에 0인지 아닌지 확인하는 코드로는 이전으로 돌아가는 걸 막기 힘들었었다. 하지만 곰곰히 생각해보니 맨 처음에 그래프의 시작이 1이었고, graph[ny][nx] = graph[y][x] + 1을 해나가기 때문에 내가 이동할 경로만 1이 된다는 사실을 알았다. 따라서 graph[ny][nx] == 1일 때 다음 루트를 진행해나가면 되었다.

또 알아낸 것은 파이썬에서는 int로 이중리스트틀 작성하여도 인덱싱을 통해 int의 해당 자리를 불러올 수 있다는 것이다. 예를들어 어떤 arr의 원소가 [111000,101011,101100,100000] 이면 arr[0][2]는 1이 된다. 111000라는 정수 자체가 숫자 겸 리스트인것이다;; arr[0]은 111000이 될 것 이다.. 놀랍지 아니한가..