백준 - 2178번(BFS)

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

2178번: 미로 탐색

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

arr = []

for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().rstrip())))

def BFS():
    # 상,하,좌,우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = deque()
    q.append([0,0])

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            #조건 만족시에만 실행(arr의 범위를 벗어나면 안됨)
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                if arr[nx][ny] == 1:
                    arr[nx][ny] = arr[x][y] + 1
                    q.append([nx, ny])

    # 목적지인 arr[n-1][m-1]에 존재하는 값이 최단거리(합)
    return arr[n - 1][m - 1]

ans = BFS()

print(ans)

 

보통 전체 탐색인 경우 DFS, BFS 상관없이 사용 가능하다.

다만 최단거리, 최소갯수 이런 최소가 나오면 보통 BFS를 쓰는 게 일반적이다.

그리고 이런 최단거리 최소횟수 문제는 보통 조건이 하나 추가될 때마다 문제가 2배씩 어려워지는 기분이다.

다행히 이 문제는 조건이 하나밖에 없다. 1만 지나갈 수 있다는 것이다.

또한 이 문제는 반드시 0,0 에서 시작하고 미로가 정상적으로 완주할 수 있는 경우만 주어지는 아주 친절한 문제다.

BFS 탐색을 통해서 이전까지 횟수의 +1 만큼 해주고 조건을 만족해서 이동한 좌표들을 q에 넣어준다.

최종적으로 n-1,m-1 까지 탐색을 마치면 n-1, m-1의 좌표에 존재하는 값이 최단거리 이동 횟수의 누적 값이다.