BFS : 미로 탐색(백준 2178번)

▶ 문제 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

##### 문제 #####
# N×M크기의 배열로 표현되는 미로가 있다.
# 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 
# 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 
# (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 
# 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
# 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

##### 입력 #####
# 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 
# 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 
# 각각의 수들은 붙어서 입력으로 주어진다.

##### 출력 #####
# 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 
# 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

▶ 접근 방법

방문 탐색을 하는 과정에서 탐색의 결과가 어떻게 최소인지를 보장할 수 있는가가 관건이었다.
아래 문제 풀이 코드에서 DFS가 아닌 BFS를 사용한 이유가 여기에 있다.
DFS와 달리 BFS는출발 정점에서 가장 가까운 정점부터 순서대로 탐색을 진행하기에
최단 거리를 보장할 수 있는 것이다.

 

▶ 풀이 코드

import sys
from collections import deque

# N = row의 수, M = column의 수
N, M = map(int, sys.stdin.readline().split())

# 입력 값을 바탕으로 미로 리스트를 만든다.
maze = []
for _ in range(N):
    maze.append(list(map(int, input())))

# 방문 여부를 0으로 표시한 리스트를 만든다.
visited = [[0] * M for _ in range(N)]

# BFS에 사용할 queue를 만든다.
queue = deque()
queue.append((0, 0))

# 시작 칸을 1로 바꾼다.
visited[0][0] = 1

# queue가 있는 동안 반복한다.
while queue:
    x, y = queue.popleft()

    # 시작 칸의 상, 하, 좌, 우를 모두 살핀다.
    for dir_x, dir_y in (-1, 0), (1, 0), (0, -1), (0, 1):
        new_x, new_y = x + dir_x, y + dir_y

        # 새로운 칸이 N행, M열보다 작고 0행, 0열보다 크거나 같다면
        if 0 <= new_x < N and 0 <= new_y < M:
            # 새로운 칸이 이동 가능한 곳인지, 그리고 방문했던 곳인지 확인한다.
            if maze[new_x][new_y] == 1 and visited[new_x][new_y] == 0:
                # 방문 표시를 해준다. 이때 이전까지 방문했던 곳의 정보들을 바탕으로 갱신한다.
                visited[new_x][new_y] = visited[x][y] + 1
                # 새로운 칸을 queue에 넣는다.
                queue.append((new_x, new_y))

    # 만약 마지막에 도착하면 지금까지 방문하면서 갱신해주었던 값을 출력한다.
    if x == N - 1 and y == M - 1:
        print(visited[x][y])

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?

2021.11.19 - [알고리즘] - DFS & BFS : DFS와 BFS(백준 1260번)

2021.11.19 - [알고리즘] - DFS & BFS : 연결 요소의 개수(백준 11724번)

2021.11.19 - [알고리즘] - DFS & BFS : 바이러스(백준 2606번)