https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
* 풀이
BFS 로 풀이함.
1. 아이디어
- 방문 X && 길이 맞음 -> BFS
2. 시간 복잡도
- O(V+E)
- V: 100*100
- E: 4*100*100
- V+E: 5000000=500만
3. 자료구조
- 방문 여부: chk[][]
길이 맞는지 확인: map[][]
4. 로직 순서
1) 미로판 범위 내에서
2) map[0][0] 부터 bfs 를 이용해 동,서,남,북 4방향을 검사하여 이동 했을 때 1이며, 방문하지 않은 곳을 찾는다.
3) 여기서 값이 1이면, 이전의 값에 +1 해서 이동할 때 지나야 하는 최소의 칸 수를 더해준다.
4) 좌표가 제일 오른쪽 아래까지 오면 그 좌표의 체크 배열 값을 출력해준다.
5. 발생했던 오류
map에 값을 넣을때 아래와 같이 단순히 split 만 해주었을 경우에 list index 오류가 발생했다.
map = [list(map(int, input().split())) for _ in range(n)]
디버거를 통해 확인해보니 map 에 값이 이상하게 들어가 있었다.

방문여부를 확인해주는 chk는 , 를 구분자로 해서 제대로 6*4 행렬로 들어갔는데, map은 구분자 없이 들어가게 되어 index를 통해 비교하는 부분에서 에러가 발생했던 것 이다.
그래서 공백을 제거하는 함수인 strip() 함수를 사용해서 map 을 생성해 주었더니 아래와 같이 정상적으로 map 이 생성되었다.

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
map = [list(map(int, input().strip())) for _ in range(n)]
# 방문 했는지 확인
chk = [[False] * m for _ in range(n)]
# 이동할 4가지 방향
dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs(y, x):
q=deque()
chk[0][0] = 1 # 출발
q.append((y, x))
while q:
ey, ex = q.popleft()
# 현재 위치에서 4가지 방향으로 위치 확인
for k in range(4):
ny = ey + dy[k]
nx = ex + dx[k]
if 0<= ny <n and 0<= nx <m:
if map[ny][nx] == 1 and chk[ny][nx] == 0: # 길이 있고, 아직 방문 안했으면
chk[ny][nx] = chk[ey][ex] + 1 # 몇 번째 방문인지 현재 좌표의 방문 값에 1을 더해줌
q.append((ny, nx))
return chk[n-1][m-1] # 방문 배열의 가장 마지막 요소를 출력하면 몇 번째 만에 도착인지 알 수 있다.
print(bfs(0,0)) # 첫 번째 위치가 문제에 주어져 있음
'Coding Test > Python' 카테고리의 다른 글
| [Python] 소수(에라토스테네스 체) (1) | 2023.01.17 |
|---|---|
| [Python] 대표값 (0) | 2023.01.11 |
| [Python] K번째 큰 수 (0) | 2023.01.11 |
| [백준] 2606 바이러스 (BFS) (0) | 2022.04.21 |
| [백준 ] 2667 단지번호붙이기 (BFS) (0) | 2022.04.18 |