[백준] 2178번 미로 탐색 Python3 - BFS

문제와 입출력

예시 입출력

 

시간 복잡도와 공간 복잡도

입력 조건

 

제한

 

N과 M의 최댓값은 100이기에 미로의 최대 크기는 10000이다. 미로 탐색을 10000번 하더라도 1초에 2000만번 연산이 가능한 Python3에 10000번의 연산은 그리 무거운 연산이 아니다. 시간 복잡도는 O(n^3) 이상만 아니면 될 거라고 생각했다.

---

자연어 알고리즘과 코드

참고) 2차원 리스트 graph의 요소 값이 1이면 처음 방문한 좌표, 0이면 벽, 음수면 맵 범위 밖이다.

만약, graph의 좌표 값이 2이상 양수면 시작 점으로부터 그 좌표까지의 거리를 의미한다.

 

1. 미로 그래프와 상하좌우 방향을 지정하는 리스트를 생성한다.

2. 시작 지점을 0,0으로 설정하여 미로  탐색을 시작한다.

3. queue에 시작 지점 좌표를 append 한다.

4. qeueue의 front에 있는 현재 좌표 정보를 popleft(dequeue) 한다.

5. 현재 좌표에서 상하좌우로 각각 한칸 씩 이동하여 다음 좌표를 찾는다

 

• 만약, 다음 좌표가 맵 범위를 벗어나면 다음 방향으로 넘어간다.
• 만약, 다음 좌표가 벽에 도달하면(0) 다음 방향으로 넘어간다.
• 다음 좌표로 처음 방문한 좌표(1로 설정됨)에 도달하면 현재 좌표의 값에 +1 하여 다음 좌표의 값을 설정한다

6. 다음 좌표의 값을 queue에 enqueue(append) 한다.

7. 4~6 과정을 queue가 빌 때까지 한다.

8. 미로 탐색이 끝나면 graph[n-1][m-1]을 리턴하고 출력한다.

from collections import deque
import sys

input = sys.stdin.readline
n,m = map(int, map(int, input().split()))

# 상, 하, 좌, 우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 미로 생성
graph = []
for i in range(n):
    graph.append(list(map(int, input().rstrip())))

# 미로 탐색
def bfs_maze(x,y):
    queue = deque()
    queue.append((x,y))

    # queue가 empty가 될때까지 반복한다.
    while queue:
        #현재 좌표
        x,y = queue.popleft()

        #현재 좌표에서 상,하,좌,우로 움직인다.
        for i in range(4):
            # 다음 좌표
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 다음 좌표가 미로를 벗어난다면 pass
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            # 다음 좌표가 벽(0)이라면 pass
            if graph[nx][ny] == 0:
                continue
            
            # 다음 좌표가 벽(1)이라면 다음 좌표의 값을 현재 좌표의 값 + 1로 설정한다.
            # graph의 요소 value는 0,0 시작으로부터 그 좌표까지 이동 거리를 의미한다.
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))

    # 최종 이동 거리를 반환한다.
    return graph[n-1][m-1]

print(bfs_maze(0,0))# 미로 탐색 호출

---

세 줄 요약

1. 새로운 방식의 BFS 탐색법

2. Graph의 요소 값이 2이상의 양수면 시작 점으로부터 그 좌표까지의 이동 거리이다.

3. 조건 별로 잘 체크하자

---