[백준] 2178번 - 미로탐색

---

문제 분석

N, M의 최대 데이터 크기가 100으로 매우 작기 때문에 시간 제한은 별도로 생각하지 않아도 된다.
문제의 요구사항은 지나야 하는 칸 수의 최솟값을 찾는 것으로, 최단거리 문제이기 때문에 BFS를 떠올릴 수 있다.
해당 문제의 조건에 따라 완전 탐색을 진행하면서 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 방식으로 진행하고, BFS를 사용하여 최초로 목적지 (N,M)에 도달했을 때의 깊이를 출력하면 된다.

---

소스 코드

# 미로 탐색

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

N, M = map(int, input().split())
arr = [[0 for col in range(M + 2)] for row in range(N + 2)]
visit = [[False for col in range(M + 2)] for row in range(N + 2)]
Result = 0
success = False
deq = deque()

for i in range(1, N + 1):
    values = input()
    for j in range(1, M + 1):
        arr[i][j] = values[j-1]

deq.append((1, 1))

while True:
    testDeq = deque()
    check = False
    Result += 1
    while deq:
        x, y = deq.popleft()
        visit[x][y] = True
        if x == N and y == M:
            success = True
            break
        if arr[x][y-1] == '1' and not visit[x][y-1]:
            visit[x][y-1] = True
            testDeq.append((x, y-1))
            check = True
        if arr[x-1][y] == '1' and not visit[x-1][y]:
            visit[x-1][y] = True
            testDeq.append((x-1, y))
            check = True
        if arr[x][y+1] == '1' and not visit[x][y+1]:
            visit[x][y+1] = True
            testDeq.append((x, y+1))
            check = True
        if arr[x+1][y] == '1' and not visit[x+1][y]:
            visit[x+1][y] = True
            testDeq.append((x+1, y))
            check = True
    if success:
        print(Result)
        break
    if not check:
        break
    else:
        while testDeq:
            X, Y = testDeq.popleft()
            deq.append((X, Y))            

---

문제를 푸는 과정에서 arr배열에 대해 어떻게 만들면 좋을 지 고민을 하였고, 기존에 주어진 N,M값보다 2개씩 더 큰 배열을 0으로 초기화 하여 만들어서 주어진 입력대로 해당 인덱스에 값을 넣는 방식으로 구현하였다.
즉, 0부분은 가지 못하게 되고, 1부분에 대해서만 접근이 허용되므로 특정 인덱스에서 상하좌우의 값을 찾을 때 0으로 미리 초기화 해두면 index가 Bound를 벗어나는 에러에 대해서 처리가 가능하며 또한 주어진 대로 1만을 파악할 수 있다.