[백준] 1261번 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

 

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

 

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

 

풀이

이 문제는 대표적으로 다익스트라를 이용하여 풀 수 있지만 0-1 BFS라는 방법으로 구현할 수 있기 때문에
그 방법을 이용해서 문제를 풀어보려고한다.

0-1BFS는 가중치가 모두 0 아니면 1로 구성되어 있는 그래프에서 사용할 수 있다.
임의의 정점 u에서 BFS가 실행된다고하면 다익스트라처럼 최단거리가 줄어든 경우에만 큐에 삽입한다.
그렇다면 큐는 항상 기준점에 대한 거리로 정렬되어 있는 상태가 된다.

BFS에서 생기는 깊이에 대한 부분을 0과 1에 대응시켜보면
가중치가 0인 경우에는 현재 노드와 같은 깊이에 있는 노드를 나타내고,
가중치가 1인 경우에는 현재 노드보다 1단계 depth가 높은 경우를 나타낸다.

BFS는 같은 깊이에 있는 노드를 모두 탐색한 뒤 다음 노드를 탐색하기 때문에 큐에는 깊이 순으로 들어가게된다.
하지만 단순히 그래프에 인접한 영역만 파악하여 순서대로 큐에 삽입하게 된다면

위와 같은 그림이 있다고 했을때 start와 입전한 0과 1이 삽입된 후 0과 인접된 0은 1 뒤에 들어가기 때문에 같은 깊이지만 더 늦게 수행되게 된다. 이런 문제를 막기 위하여 Heap이나 Priority Queue를 이용하게되면 자료구조 정렬을 위하여 
O(logN)이 수행되기 때문에 O(1)로 수행할 수 없게 된다. 

 

하지만 여기서는 가중치가 0과 1만 있기 때문에 Deque 구조를 이용하여 가중치가 0인 경우에는 앞에 삽입하고
1인 경우에는 뒤에 삽입하는 것으로 같은 깊이에 있는 정점에 먼저 방문하게 할 수 있게된다.

 

전체 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
matrix = []
#파괴한 블럭의 갯수를 저장한 matrix
distroy = [[-1 for _ in range(N)] for _ in range(M)]
distroy[0][0] = 0
for i in range(M) :
    matrix.append(list(sys.stdin.readline().strip()))


        #상     하     좌     우
dir = [[-1,0],[1,0],[0,-1],[0,1]]



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

while dq :
    y, x = dq.popleft()
    for i in range(4) :
        next_y, next_x = y +dir[i][0], x+dir[i][1]
        if next_x >= 0 and next_x < N and next_y >= 0 and next_y < M :
            if distroy[next_y][next_x] == -1 :
                if matrix[next_y][next_x] == '0' :
                    dq.appendleft([next_y,next_x])
                    distroy[next_y][next_x] = distroy[y][x]
                elif matrix[next_y][next_x] == '1' :
                    dq.append([next_y,next_x])
                    distroy[next_y][next_x] = distroy[y][x] + 1

print(distroy[-1][-1])

4 방향에 대하여 범위 밖이 아닌지만 체크하고 위에 설명한 0 - 1 BFS방식으로 구현하면 답을 얻을 수 있다.
다익스트라와 다르게 BFS에서는 같은 곳을 2번 방문할 필요가 없기 때문에 distroy배열을 이용하여 파괴한 벽의 갯수가 갱신되었는지 체크했다.
(일반적인 dist 배열은 distance로 거리를 나타내는 배열)