[BJ2178] 미로 탐색

백준 알고리즘

🚩 문제 설명

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

◾ 1 일 경우 ➡️ 지날 수 있음.

◾ 0 일 경우 ➡️ 지날 수 없음.

 

 

 

---

 

 

 

✅ 입출력

1) 두 정수 N, M이 주어진다. : 미로의 크기
2) 다음 N개의 줄에 M개의 정수로 미로가 주어진다.
return ➡️ 지나야하는 최소의 칸 수를 출력.

✔️ 예제 1

4 6
101111
101010
101011
111011

15

 

✔️ 예제 2

4 6
110110
110110
111111
111101

9

 

✔️ 예제3

2 25
1011101110111011101110111
1110111011101110111011101

38

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
maze = [[int(i) for i in sys.stdin.readline().strip()] for n in range(N)]
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 사용
➡️  좌표를 이동하여 상하좌우를 확인한다.

◾ 최소의 칸 수를 적으면서 이동

◾ (N, M)에 해당되었을 때 return 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

➕ 참고

https://yeomss.tistory.com/133?category=985628 

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

 

# 백준 미로탐색 python 파이썬

# 백준 2178 미로 탐색 파이썬 python

---