[BFS / DFS] 백준 2178번: 미로 탐색 (BOJ 2178) 풀이

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
board = []
for _ in range(n):
    row = list(map(int, list(input().split()[0])))
    board.append(row)

def solution(n, m, board):
    visited = [[-1]*m for _ in range(n)]
    
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    q = deque()
    q.append((0, 0))
    visited[0][0] += 1
    while q:
        x, y = q.popleft()
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
            if board[nx][ny] == 0 or visited[nx][ny] != -1: continue
            q.append((nx, ny))
            visited[nx][ny] = visited[x][y] + 1
    
    return visited[n-1][m-1]+1

print(solution(n, m, board))

☆ 해설

• (바킹독님 강의 참고) visited 배열 초기값을 -1로 두면, 방문여부와 동시에 거리도 측정할 수 있음.
• 시작점을 큐에 넣고, 네 가지 방향을 돌면서 큐에 넣고 빼기를 반복하면서 확장.
• 반드시 길이 있다고 했기 때문에, 해당 목적지의 visited 배열의 값에 +1을 해준 것이 최종 거리.

+ "각각의 수들은 붙어서 입력으로 주어진다." <- 이 조건을 처리하기 위해 아래와 같은 작업을 수행함.

+ input().split()은 문자열 리스트를 반환함. 따라서, input().split()[0]을 하면 문자열을 뽑아낼 수 있음. ex) "101111"

+ 문자열을 list()로 감싸면, 각 문자를 원소로 갖는 리스트를 생성할 수 있음. 따라서, str = "101111"의 경우, list(str)을 하게 되면 ['1','0','1','1','1','1']의 형태로 리스트를 생성할 수 있음. 이 리스트를 map을 돌려서 int로 바꾼 뒤 리스트 형태로 다시 바꿔주면 평상시에 다루던 정수 리스트로 변환시킬 수 있음.