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

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

2178번: 미로 탐색

BFS로 구현하는 문제. 해당 위치까지 최단경로로 이동하는 문제입니다. 해당문제를 단순히 재귀로 구현할 경우, 굉장히 까다로워 집니다. 왜냐하면, 상하좌우 방향 순서에 따라 도착하는 최단 경로가 달라집니다. 이에 대한 설명은 아래에서 하겠습니다. 따라서 Queue를 이용하여 BFS를 구현한 후, 문제를 해결할 수 있습니다. 유사한 문제로 7576번 토마토 문제를 푸시면 됩니다.

 

※ 고려사항

1. 입출력 구현

2. BFS 구현

---

1. 입출력 구현

입력은 공백없이 2차원 행렬을 입력받습니다. 그래프 문제에서 굉장히 기본적인 부분입니다. strip 메소드를 이용하여 구분해 줍니다. 자세한 내용은 제 블로그 그래프 부분을 참고해주세요!

또 상하좌우로 움직여야 하기 때문에, 이를 받아줄 x, y값을 만들어 줍니다. 코드는 다음과 같습니다.

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
matrix = [list(map(int, input().strip())) for _ in range(n)]

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

 

2. BFS 구현

해당문제는 재귀로 구현을 하게 되면, 굉장히 까다롭습니다. 그 이유는 각 위치에서 상하좌우로 움직이게 되는데 예를 들어, 상 -> 하 -> 좌 -> 우 순서로 움직일때 상 방향에서 조건이 만족되면 그 방향이 종료될때까지 진행됩니다. 그러나 이 문제에서는 각 방향으로 모두 움직인 뒤에, 거리가 각 방향별로 1 증가 되어야합니다. 따라서 Queue를 이용한 BFS를 구현해야 합니다.

Queue를 이용해 초기 위치를 저장한 후, 상하좌우로 이동한 위치의 값이 1이면서, 범위를 벗어나지 않는다면, 해당위치를 순서대로 Queue에 삽입합니다. Queue가 모두 비워지면, 코드는 종료되며, 마지막 (n, m) 행렬에 저장된 값이 최단거리값이 됩니다. 코드는 다음과 같습니다.

# BFS
def bfs(x, y):
    
    # Queue 생성
    queue = deque([])
    queue.append([x, y])

    while queue:

        # 가장 최근 값 pop
        x, y = queue.popleft()

        # 상하좌우
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            # 범위내에 존재하면서, 1인데 방문되지 않았으면
            if (0 <= nx < n) and (0 <= ny < m) and matrix[nx][ny] == 1:

                # 현재위치 + 1
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

---

전체코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
matrix = [list(map(int, input().strip())) for _ in range(n)]

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

# BFS
def bfs(x, y):
    
    # Queue 생성
    queue = deque([])
    queue.append([x, y])

    while queue:

        # 가장 최근 값 pop
        x, y = queue.popleft()

        # 상하좌우
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            # 범위내에 존재하면서, 1인데 방문되지 않았으면
            if (0 <= nx < n) and (0 <= ny < m) and matrix[nx][ny] == 1:

                # 현재위치 + 1
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

# 출력               
bfs(0, 0)
print(matrix[n-1][m-1])

 

---

이와 유사한 토마토 문제를 풀기 전에, 이 문제를 풀어봤었다면, 아마 코드를 구현하는데 어려움이 있었을 겁니다. 순서상 해당문제를 해결한 후에, 토마토 문제를 푸는것이 맞는듯한데, 어쩌다보니 순서가 바뀌었네요 ㅎㅎ

최근 그래프와 분할정복을 집중적으로 학습하는데, DFS, BFS를 제외하고 Prim, 다엑스트라, 플로이드 - 워셜 등과 같은 그래프 문제에 도전해야 할 것 같습니다.

설명의 오류나, 궁금하신 점은 언제든 피드백해주시면 감사하겠습니다 ^~^