미로 탈출
유형 : 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 파이썬
코딩 테스트, 어디서부터 그리고 어떻게 준비해야될까? 이제 졸업 혹은 졸업을 앞두신 분들 그리고 개발 관련 취업에 종사하시고 싶은 분들이라면 반드시 놓치지 말아야할 점이 바로 코딩 테스
muns-da2.tistory.com
반응형
'Programming Test > 알고리즘' 카테고리의 다른 글
[알고리즘 공부] 성적이 낮은 순서로 학생 출력 (0) | 2024.03.30 |
---|---|
[알고리즘 공부] 위에서 아래 (0) | 2024.03.28 |
[알고리즘 공부] 음료수 얼려 먹기 (0) | 2024.03.24 |
[알고리즘 공부] 게임 개발 (0) | 2024.03.24 |
[알고리즘 공부] 왕실의 나이트 (0) | 2024.03.22 |