[DFS/BFS/완전탐색] ▲ 2178번 - 미로 탐색

[백준] 2178번 - 미로 탐색

풀이 시간: 30~40분 이내

 

1) 문제 해결 아이디어

이 문제는 시작 위치(1, 1)에서 도착 위치(N, M)으로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제다.

즉, 최단 경로를 구하는 문제로 BFS로 풀 수 있는 대표적인 문제이다.

BFS로 문제를 풀어야 한다는 것은 알았으나 방문 처리를 할 때 기록해야하는 값을 전역변수로 변경, 대입하여 약간의 어려움을 겪었다.

 

첫번째 오류. 최소 이동 칸 수를 구하기 위해 전역변수를 쓴 것

처음에 이동 칸 수를 나타낼 전역변수(res)를 선언하고 popleft()할 때마다 res 값을 1 증가했다.

상하좌우를 탐색할 때 갈 수 있는 칸이면 큐에 삽입하고 방문처리를 하는데 칸의 값을 res를 넣어주려고 했다. 그리고 마지막에 (n -1, m - 1) 위치의 값을 출력시키는 형태로 코드를 짰다.

하지만 이렇게 되면 pop할 때마다 res 값을 증가하는 꼴이므로 결국에 res값은 갈 수 있는 모든 칸 

즉, 미로에서 1인 칸의 개수가 된다.

 

BFS에서 최소 이동 칸 수를 구할 때

인접(상하좌우) 좌표의 값이 현재 좌표의 값에 1을 더한 값이 되어야 한다!!!

 

만약, 이전처럼 시작 좌표 기준으로 인접한 좌표들(그래프 전체 노드)의 개수를 구할 때는

전역변수를 선언하고 popleft() 할 때마다 그 값을 1씩 증가시키면된다!

 

2) 소스코드

from collections import deque

n, m = map(int, input().split())  # 목표 좌표
# 0: 이동 불가, 1: 이동 가능
graph = [list(map(int, input())) for _ in range(n)]

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS
def bfs(x, y): 
  # 시작 좌표 삽입, 방문 처리
  queue = deque()
  queue.append((x, y))
  graph[x][y] = 1  # 갈 수 없는 길로 변경

  while queue:
    x, y = queue.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] == 1):
          queue.append((nx, ny))
          graph[nx][ny] = graph[x][y] + 1 

bfs(0, 0)
print(graph[n-1][m-1])

[참고] https://jokerldg.github.io/algorithm/2021/03/24/maze.html

백준 2178번 미로 탐색 (python 파이썬) - Tech