[백준] 2178 미로 탐색 (BFS)

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

2178번: 미로 탐색

* 풀이

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)) # 첫 번째 위치가 문제에 주어져 있음