[알고리즘 공부] 미로 탈출

미로 탈출

유형 : BFS

출처 : 이것이 취업을 위한 코딩 테스트다. with Python

프로그램 언어 : Python

난이도 : ★ 

 

규칙

 아무개는 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야한다. 아무개의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 아무개가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력조건

• 첫째 줄에 두 정수 N, M (4<=N, M<=200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 또는 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

입력 예시
5 6
101010
111111
000001
111111
111111

출력 예시
10

 

from collections import deque

# 행(n)과 열(m)의 입력을 받습니다
n, m = map(int, input().split())

array = []

# 미로 입력 받기, 0은 벽이고 1은 길입니다
for i in range(n):
    array.append(list(map(int, input())))

print(array)

# 이동 방향 정의: 상, 하, 우, 좌
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 너비 우선 탐색(bfs) 함수로 최단 경로 찾기
def bfs(x, y):
    # 시작점을 큐에 넣기
    queue = deque()
    queue.append((x, y))

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 첫 번째 요소를 꺼냄
        x, y = queue.popleft()

        # 가능한 모든 이동(상, 하, 우, 좌)을 시도
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 미로의 경계를 넘어가는지 확인
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            
            # 해당 칸이 벽인 경우 건너뜀
            if array[nx][ny] == 0:
                continue
            
            # 유효한 이동인 경우, 해당 칸을 거리로 표시하고 큐에 추가
            if array[nx][ny] == 1:
                array[nx][ny] = array[x][y] + 1
                queue.append((nx, ny))
    
    # 우측 하단 구석까지의 거리 반환
    return array[n-1][m-1]

# 시작점에서 우측 하단 구석까지의 최단 거리 출력
print(bfs(0,0))

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬