[백준] 2178번 : 미로 탐색 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2178번: 미로 탐색

 

1. 문제 설명

2. 풀이과정

알고리즘 분류에 그래프 탐색과 너비 우선 탐색이 있길래 2차원 그래프를 만들고 너비 우선 탐색으로 해결해보려고 했으나 쉽지 않았다.

끊임없는 고민을 하던 중 시간이 초과되더라도 모든 경우의 수를 생각해 보기로 했다. 하여 각 자리마다 상, 하, 좌, 우로 이동할 수 있는 경우를 생각해 보았다.

모든 경우를 생각하던 중 다음 위치로 이동하기 위해서 최소 얼마의 이동이 있었는지 기억해 두면 마지막 칸까지 모든 경우의 수를 확인했을 때 최소한의 이동 거리를 구할 수 있겠다는 생각을 하게 되었다.

각 위치별로 이동을 하고 최소 이동 거리를 계산할 때는 연산 속도가 빠른 deque 자료구조를 사용하기로 했다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 최소 이동 거리 연산에서 deque 자료구조를 활용하기 위해 deque 모듈을 불러온다. from collections import deque
3. 함수는 아래에서 자세하게 살펴본다. def BFS(row, col)
4. 미로의 행과 열의 크기를 입력받는다. N, M = map(int, sys.stdin.readline().split())
5. 각 위치별로 최소 이동 거리의 결과를 저장해 줄 그래프를 생성한다. graph = list()
6. 각 위치별로 초기 칸의 정보를 입력받는다. 입력은 행의 개수만큼 반복하며 각 행의 정보를 입력받고 각 행의 정보는 enter로 구분되어 입력이 받아지기 때문에 마지막 enter는 지워서 포함시키지 않고 저장한다. for i in range(N): graph.append(list(map(int, sys.stdin.readline().rstrip())))
7. 각 위치별로 4가지 방향에 따른 결과가 존재하므로 네 방향으로 이동한 결과의 행과 열 변환 값을 저장한 리스트를 생성한다. move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
8. 생성해 준 너비 우선 탐색 함수에서 초기 시작 위치의 인덱스 값인 0, 0을 대입하고 그 계산 결과를 출력한다. print(BFS(0, 0))

 

BFS() 함수 (너비 우선 탐색 함수)

1. 너비 우선 탐색 연산을 빠르게 하기 위해 리스트가 아닌 deque 자료구조를 사용한다. queue = deque()
2. 초기 시작 위치의 행과 열의 위치를 배열로 묶어 추가한다. queue.append([row, col])
3. 생성한 deque이 공백이 될 때까지 반복한다. while (queue)
4. 가장 먼저 넣은 값을 삭제하고 삭제한 값을 추출한다. row, col = queue.popleft()
5. 4가지 방향으로 갈 수 있는 경우의 수를 모두 확인한다. for i in range(len(move))
6. 각 방향 별로 다음 행과 열의 위치를 계산한다. nextRow = row + move[i][0]  nextCol = col + move[i][1]
7. 만약 계산한 다음 위치가 각 행(N)과 열(M) 범위 안에 있고 미로에서 이동할 수 있는 위치이면 (1로 표시된 위치이면) if (0 <= nextRow < N and 0 <= nextCol < M and graph[nextRow][nextCol] == 1)
8. 다음 위치의 행과 열의 값을 추가한다. queue.append([nextRow, nextCol])
9. 그래프의 계산한 다음 위치에 이전 위치에서 1을 더한 값을 대입하여 다음 위치까지의 최소 이동 거리를 저장한다. graph[nextRow][nextCol] = graph[row][col] + 1
10. 모든 가능한 연산이 끝나면 그래프의 마지막 위치의 값을 반환한다. return graph[N - 1][M - 1]

반응형

3. 소스코드

import sys
from collections import deque

def BFS(row, col):
    queue = deque()
    queue.append([row, col])

    while (queue):
        row, col = queue.popleft()

        for i in range(len(move)):
            nextRow = row + move[i][0]
            nextCol = col + move[i][1]

            if (0 <= nextRow < N and 0 <= nextCol < M and graph[nextRow][nextCol] == 1):
                queue.append([nextRow, nextCol])
                graph[nextRow][nextCol] = graph[row][col] + 1

    return graph[N - 1][M - 1]

N, M = map(int, sys.stdin.readline().split())

graph = list()
for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))


move = [[-1, 0], [1, 0], [0, -1], [0, 1]]

print(BFS(0, 0))