[python] 백준 2178번 미로 탐색

백준 2178번 미로 탐색

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

문제

풀이

이것도 역시 BFS. 최단 경로는 BFS.
이것이 취업을 위한 코딩 테스트다의 미로 탈출 문제와 똑.같.

from collections import deque

n, m = map(int, input().split())

graph = []
for i in range(n):
    line = input().strip()  # 문자열로 처리
    graph.append(list(map(int, line)))  # 각 문자를 정수로 변환

def bfs(graph, n, m):
    queue = deque([(0, 0, 1)])  # 시작점 (0, 0)에서 시작하며, 시작 카운트는 1로 설정
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True

    while queue:
        x, y, count = queue.popleft()
        if x == n-1 and y == m-1:
            return count

        # 상
        if x - 1 >= 0 and not visited[x-1][y] and graph[x-1][y] == 1:
            queue.append((x-1, y, count + 1))
            visited[x-1][y] = True

        # 하
        if x + 1 < n and not visited[x+1][y] and graph[x+1][y] == 1:
            queue.append((x+1, y, count + 1))
            visited[x+1][y] = True

        # 좌
        if y - 1 >= 0 and not visited[x][y-1] and graph[x][y-1] == 1:
            queue.append((x, y-1, count + 1))
            visited[x][y-1] = True

        # 우
        if y + 1 < m and not visited[x][y+1] and graph[x][y+1] == 1:
            queue.append((x, y+1, count + 1))
            visited[x][y+1] = True

    return -1  # 만약 출구에 도달할 수 없다면 -1 반환

result = bfs(graph, n, m)
print(result)

direction 쓰거나 dx, dy 쓸 수도 있지만 ... 노가다 최고 하하.

📌 주의

• input() 은 문자열. 통으로 입력 받고 ex.1001 하나씩 쪼개서 리스트로 넣기. [1,0,0,1] list(map(int,변수))
• input().split() 은 공백 제거용
• 문제 풀 때 혹시 모르니 도착점에 도달할 수 없는 경우, return -1 해주기