[TC0502] [DFS/BFS] 미로 탈출

이코테

🚩 문제 설명

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

 

 

 

 

---

 

 

 

✅ 입출력

1) 첫째 줄에 N, M 이 주어진다.
2) 다음 N개의 줄에 각각 M개의 정수가 주어진다.
return ➡️ 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수

✔️ 예제 1

5 6
101010
111111
000001
111111
111111

10

 

✔️ 예제 2

3 3
110
010
011

5

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split()) # 미로의 크기 N x M
maze = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(N)] # 미로
ans = 1

steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(r, c):
    queue = deque()
    queue.append((r, c))

    while queue:
        r, c = queue.popleft()

        for s in steps:
            r_ = r + s[0]
            c_ = c + s[1]

            if r_ < 0 or c_ < 0 or r_ >= N or c_ >= M:
                continue

            if maze[r_][c_] == 0:
                continue

            if maze[r_][c_] == 1:
                maze[r_][c_] = maze[r][c] + 1
                queue.append((r_, c_))

    return maze[N-1][M-1]

print(bfs(0, 0))

💬 Point

➡️  큐를 사용하여 bfs를 구현

◾ 만약 maze[r_][c_]가 1에 해당한다면 해당 노드에 1을 더해서 넣는다.

◾ 큐에 (r_, c_) 을 추가한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 이코테 미로 탈출 파이썬 python

# 이것이코딩테스트다 미로탈출 파이썬 python

---