[백준] 2178 미로탐색 - 파이썬(그래프 탐색)

문제링크

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

2178번: 미로 탐색

 

사실 bfs 문제들은 처음 접해본다.

이러한 문제들은 어떻게 푸는지 자문을 구해보았을 때 문제를 보고 답을 한번 본 후 코드를 뜯어보라는 조언을 받았다.

 

graph라는 리스트를 만든 후 2차배열로 graph안에 넣어주는 것이 첫번째 순서이다.

 

2차원 배열에서 인덱스는 밑으로 가면서 증가하고 위로 가면서 감소하므로 dx = [-1,1,0,0] 으로 위 아래 방향으로 설정해준다.

같은 방식으로 dy = [0,0,-1,1] 로 설정한다. (인덱스가 왼쪽으로 가면 감소, 오른쪽으로 가면 증가하므로)

 

queue는 양옆에서 삽입, 삭제가 가능한 deque로 지정해주고 처음 받은 좌표를 큐에 넣어준다.

while queue라는 조건으로 queue의 값이 존재할때만 while문이 실행되도록 설정한다.

 

처음에는 queue에 있던 값을 삭제하고 시작한다.

for문에서 4번 반복하면 상하좌우 한번씩 실행하도록 설정한다.

nx, ny가 0보다 작거나 입력받은 값 N,M보다 크거나 같으면 그래프의 범위를 벗어나므로 continue를 사용해 for문을 다시 실행시킨다.

또한 graph[nx][ny] 값이 0이면 벽이므로 이동할 수 없으니 continue를 사용한다.

graph[nx][ny] 값이 1이면 벽이 아니므로 이동시키는데 이 때 움직인 칸 수를 더해줘야 하므로 1을 더해준다.

 

처음에 x,y에서 시작하고 그 다음 움직인 nx,ny가 다시 시작점이 되어 반복해주면 n,m까지의 이동횟수를 구할 수 있다.

from collections import deque
import sys

N, M = map(int, sys.stdin.readline().split())

graph = []

for _ in range(N):
  graph.append(list(map(int, input())))

# 너비 우선 탐색
def bfs(x, y):
  # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
  dx = [-1, 1, 0, 0] 
  dy = [0, 0, -1, 1]

  # deque 생성
  queue = deque()
  queue.append((x, y))

  while queue:
    x, y = queue.popleft()
    
    # 현재 위치에서 4가지 방향으로 위치 확인
    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
      
      # 벽이므로 진행 불가
      if graph[nx][ny] == 0:
        continue
      
      # 벽이 아니므로 이동
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1 //갯수 카운트
        queue.append((nx, ny)) //큐에 다시 추가
  
  # 마지막 값에서 카운트 값을 뽑는다.
  return graph[N-1][M-1]

print(bfs(0, 0))