문제

입력

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

출력

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

입력 예시 1

4 6
101111
101010
101011
111011

출력 예시 1

15

문제 이해

가중치가 없는 그래프에서 그래프의 최단거리를 탐색할 때는 BFS밖에 사용하지 못한다. 가중치가 없는 대부분의 그래프 탐색 문제는 DFS와 BFS, 두 가지 방법으로 모두 풀이가 가능하지만, 최단거리를 구할때는 BFS만 사용할 수 있다. 그래서 이전에 DFS 한놈만 팰때는 이 문제를 못 풀었던 거고, 그게 내가 지금 BFS를 공부하고 있는 이유이다.

이 문제는 상하좌우로 이동하면서 도착지점으로 도달하는 최단거리를 구하는 문제이다. 상하좌우가 1인지 확인하고, 그 좌표값과 거리 + 1값을 큐에 넣어주면 된다. BFS 개념을 이해한다면 쉽게 해결할 수 있다.

코드

# 백준 2178번 미로 탐색

import sys
input = sys.stdin.readline

from collections import deque

# 방향벡터
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def BFS(y, x, distance):
    global visited

    queue = deque()
    queue.append((y, x, distance))
    visited[y][x] = True

    while queue:

        y, x, distance = queue.popleft()

        # 도착지점이면 거리 출력 & 리턴
        if y == N - 1 and x == M - 1:
            print(distance)
            return

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N and game_map[ny][nx] and not visited[ny][nx]:
                queue.append((ny, nx, distance + 1))
                visited[ny][nx] = True
    # 도착지점에 도착을 못하면 -1 출력
    # 도착지점에 도착한다면 출력될 일이 없음
    print(-1)

# 0. 입력 및 초기화
N, M = map(int, input().split()) #N세로 M가로
game_map = []
visited = [[False] * (M) for _ in range(N)]

# 1. 연결 정보 입력
for i in range(N):
    game_map.append(list(map(int, input().rstrip())))

# 2. BFS호출 및 출력
BFS(0, 0, 1)