[백준_2178] 미로탐색 python

경로를 찾는 데에 bfs를 사용하든 dfs를 사용하든 자기 맘이다.

더 자신있는 것을 사용하는 쪽이 좋다.

그러나 최소 경로를 찾을 때에는 bfs를 사용해야 한다.

# n, m 입력
n, m = map(int, input().split())

# maze
maze = [
    [0] * m
    for _ in range(n)
]

# maze 채우기
for i in range(n):
    # block 입력받기
    block = input()
    for j in range(len(block)):
        # 이동할 수 있는 칸은
        if block[j] == '1':
            # 1로 표시
            maze[i][j] = 1

# visited
visited = [
    [0] * m
    for _ in range(n)
]

# step
step = [
    [0] * m
    for _ in range(n)
]

# step 첫번째 칸 1로 설정
step[0][0] = 1

# in_range(x,y)
def in_range(x,y):
    return 0 <= x and x < n and 0 <= y and y < m

# check(x, y)
def check(x, y):
    # 범위 내에 있고, 방문한 적 없고, 벽이 아니면 통과
    return in_range(x, y) and not visited[x][y] and maze[x][y]

# bfs()
def bfs():
    # 큐 안에 원소가 없을 때 까지 반복
    while q:
        
        # 언팩킹
        x, y = q.popleft()

        # dxs, dys -> 상 하 좌 우 순서 상관 x
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        
        for dx, dy in zip(dxs, dys):
            # 다음 조사 위치
            nx, ny = x + dx, y + dy
            # 그 위치가 갈 수 있으면
            if check(nx, ny):
                # 방문 위치 남겨주고
                visited[nx][ny] = 1
                # 큐에 넣어주고
                q.append((nx, ny))
                # step에 이동 횟수 기록
                step[nx][ny] = step[x][y] + 1 

# 설계
from collections import deque

# q
q = deque()

# 방문흔적 남기고
visited[0][0] = 1
# 큐에 넣어주고
q.append((0, 0))
# bfs 돌려주기
bfs()

# 출력
print(step[-1][-1])