[Python 파이썬]백준 2178번 - 미로 탐색

2023년 9월 26일

문제 링크 : 2178번 - 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

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

출력

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

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

문제 접근

시작점으로부터 도착점까지 최소 몇 칸 움직여야 도착할 수 있는 지 알아내는 문제다.

여기서 BFS를 활용해야 한다는 포인트를 빠르게 캐치할 수 있다.

또한 경로까지 구하는 것이 아닌, 지나온 최소 칸 수를 출력하는 것이기에 한 번에 한 칸씩 탐색 범위를 늘려가다 도착점을 탐색하는 그 순간까지 걸린 시간을 출력하면 된다.

(비슷한 문제 : 백준 7576 - 토마토 문제풀이)

 

문제에서 다음과 같은 조건이 주어졌다.

항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

무조건 도착지점으로 경로가 존재하도록 입력이 주어진다는 의미이니, 우리는 시작점인 (0, 0)에서 도착점인 (N - 1, M - 1)까지 최소 얼마만큼 걸리는지만 구하면 된다.

 

 

---

순서도

1. 입력값을 입력받아 N x M 사이즈의 2차원 테이블을 생성받는다.
	띄어쓰기 없이 M개의 칸이 N줄에 걸쳐 입력이 들어온다.
    한 줄 전체를 문자열 하나로 받게하여, String을 0 ~ M-1 인덱스로 참조하도록 할 것.
  
2. 방문 표시를 위한 N x M 사이즈의 2차원 배열 선언. 각 요소의 디폴트값은 False

3. 특정 좌표에서 상하좌우 한 칸씩 이동을 위해 dx, dy 선언
	탐색 횟수를 저장할 cnt를 선언. 초기값은 1

4. 방문 위치를 저장해둘 큐 선언

5. 다음 방문할 위치를 저장해둘 리스트 선언

6. 시작점(0, 0)을 시작으로 BFS 진행

7. 큐의 가장 앞에서부터 popleft()하여 추출된 좌표를 기준으로 상하좌우 한 칸씩 탐색하여
	방문할 수 있는지 확인 후, 방문 가능하면 리스트에 저장.

8. 큐에 저장된 모든 방문 위치를 방문하면 리스트에 저장된 모든 요소들을 큐로 옮김. 
	각 좌표에서 주변 한 칸 범위 내의 모든 탐색가능한 좌표들을 탐색했으니 cnt를 1 증가시킴.

9. 반복문을 계속 진행하다, popleft()하여 추출된 요소의 인덱스가 (N - 1, M - 1)이면
	cnt를 1 증가시키고 cnt를 출력. 도착점을 탐색했고 지나온 최소 칸 수를 출력했으니 exit()로 종료.

 

---

입력 예제

4 6
101111
101010
101011
111011

출력 예제

15

---

주의할 점

• 일반적인 경로 탐색이 아닌, 최소 경과 시간을 물어보는 문제는 2중 반복문을 통해 알아가야 함이 중요하다.
• 전체 코드를 보면 정답을 도출하면 해당 정답 출력과 함께 exit()로 코드를 종료시키는데 오랜만에 쓰다보니 exit(1)을 코드에 삽입했다가 디버깅 오류를 겪었다. exit() ( = exit(0) ) 과 exit(1)의 차이점은 정상 종료와 에러로 인한 강제종료이다.

---

전체 코드

# 2178

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

def bfs():
    # 오른쪽, 아래, 왼쪽, 위쪽
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    queue = deque()
    queue.append([0, 0])
    visited[0][0] = True

    next_queue = deque()

    cnt = 1

    while queue:
        while queue:
            now = queue.popleft()
            for idx in range(4):
                if isValid(now, dx[idx], dy[idx]):
                    next_v = [now[0] + dy[idx], now[1] + dx[idx]]
                    if next_v == [N - 1, M - 1]:
                        cnt += 1
                        print(cnt)
                        exit()
                    next_queue.append(next_v)
                    visited[now[0] + dy[idx]][now[1] + dx[idx]] = True
        while next_queue:
            queue.append(next_queue.popleft())
        cnt += 1
    

def isValid(now, dx, dy):
    if 0 <= now[0] + dy < N and 0 <= now[1] + dx < M:
        if board[now[0] + dy][now[1] + dx] == '1' and visited[now[0] + dy][now[1] + dx] == False:
            return True
        else:
            return False
    return False

if __name__ == "__main__":
    N, M = map(int,input().split())
    board = []
    visited = [ [False] * M for _ in range(N)]
    for _ in range(N):
        board.append(input().strip())
    
    bfs()

---

풀이 후기

일반적인 BFS 문제였다. BFS 흐름을 잘 이해하고 있다면 어렵지 않은 문제라고 생각한다.