[BOJ][⚪1][백준#02178] 미로 탐색

문제 출처

BAEKJOON Online Judge #2178

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1

1 0 1 0 1 0

1 0 1 0 1 1

1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제

예제 1

입력

4 6
101111
101010
101011
111011

출력

15```

<br>

### 예제 2

입력

```python
4 6
110110
110110
111111
111101

출력

9

예제 3

입력

2 25
1011101110111011101110111
1110111011101110111011101

출력

38

예제 4

입력

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

출력

13

My Sol

from collections import deque

def bfs():
    global mat
    Q = deque()
    Q.append((0,0))
    mat[0][0]=2

    didj = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    ti, tj = I-1, J-1
    while Q and mat[ti][tj]==1:
        ni, nj = Q.popleft()
        for di, dj in didj:
            si, sj = ni+di, nj+dj
            if not (0<=si<I and 0<=sj<J): continue
            if not mat[si][sj]==1: continue
            mat[si][sj] = mat[ni][nj]+1
            Q.append((si,sj))
    return mat[ti][tj] - 1

I, J = map(int, input().split())
mat = [list(map(int, input())) for _ in range(I)]
print(bfs())

전형적인 BFS 문제였다. 최상단의 첫 칸부터 시작해서 최하단의 끝 칸까지 도달하기까지 상하좌우에 있는 1 값의 칸만 밟아서 최소한의 경로로 도착해야한다. 벡터를 지정하여 현재 좌표와 더해 조회 좌표를 만드는데, 이 좌표가 범위를 벗어나지 않으며 값이 1인 경우에 현재 좌표의 값에서 1을 더해 덮어씌워주고, 이 탐색 좌표가 다시 현재 좌표로 해서 조회의 중앙이 될 수 있도록 Q에 append해준다.

만약 Q가 없거나 도착 지점인 mat[ti][tj]가 이전 Q의 반복 작업으로 값이 덮어씌워져 1이 아니게 되면 while문을 종료한다.

처음 시작점을 1이 아닌, 2로 두어 시작하였으므로 mat[ti][tj]에서 1을 뺀 값을 반환하여 출력하면 되겠다.

결과

맞았습니다!!

모범답안

출처

# empty