백준 2178번 미로 탐색 파이썬

리뷰

첫 2차원 배열 BFS 문제 도전이었다.. 뭔가 알것같으면서도 애매한 이 느낌

 

문제 풀이

1. BFS를 사용하기 위해 큐를 임포트 해준다.
2. 2차원 배열을 받아오고 별개로 방문을 체크해줄 배열을 False로 초기화 해준다.
3. 4방향으로 움직일 수 있으므로 방향을 나타내줄 리스트도 초기화 해준다.
4. bfs함수를 정의해 준다. 함수 인자로는 2차원 배열 리스트, 현재 x, y좌표 및 거리를 나타낼 튜플
5. while루프 실행 전 시작 위치값을 지정해 준다. x, y는 각각 0, 거리는 1
6. 움직일 수 있는 위치라면 해당 위치를 방문하여 각 거리를 계산해 준다.
7. x, y가 각각 n - 1, m - 1 위치에 도달하게 될 경우 거리를 리턴해준다.

 

참고 사항

이동 조건을 만족하여 큐에 추가할때 해당 위치를 미리 방문처리 해줘야 한다. 안그랬다가 시간 초과가 났다.

 

 

정답 코드

def q2178():
    # 백준 2178번 미로 탐색 파이썬
    from collections import deque

    n, m = map(int, input().split())
    lst = [list(map(int, list(input()))) for _ in range(n)]
    v = [[False] * m for _ in range(n)]
    dist = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def bfs(graph, start):
        q = deque([start])
        v[0][0] = True
        while q:
            x, y, d = q.popleft()
            if x == n - 1 and y == m - 1:
                return d
            for dx, dy in dist:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1 and not v[nx][ny]:
                    v[nx][ny] = True
                    q.append((nx, ny, d + 1))
    print(bfs(lst, (0, 0, 1)))
q2178()