[백준 2178 / Python] 미로 탐색

🧑🏻‍💻 문제링크

문제풀이

미로 문제는 간단하게BFS 알고리즘을 이용해서 풀면 된다. 하지만, 방향을 설정 해줘야 하기 때문에 방향을 나타낼 수 있는 dx, dy를 만들어서 위, 아래, 좌, 우를 탐색하면서 도착지점까지 최소한의 거리를 구하면 된다.

참고로 위, 아래, 좌, 우를 설정하는 방법은 다음과 같이 하면 된다.

dx = [-1, -1, 0, 0]
dy = [0, 0, -1, 1]

코드

from collections import deque

N, M = map(int, input().split())
miro = []   # 미로

# 미로를 입력
for _ in range(N):
    miro.append(list(map(int, input())))

# 방향을 나타냄
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

visited = [[0] * M for _ in range(N)]

q = deque([(0, 0)])
# 첫 번째 위치가 문제에 주어져 있으므로 1로 변경
visited[0][0] = 1

while q:
    x, y = q.popleft()

    # 미로의 끝에 도달 했을 때 해당 미로의 값을 호출
    if x == N-1 and y == M-1:
        print(visited[x][y])
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < N and 0 <= ny < M:
            if visited[nx][ny] == 0 and miro[nx][ny] == 1:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))

결과