(Python) - BOJ(1261번) : 알고스팟

https://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)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

다익스트라 또는 0-1 BFS로 해결할 수 있는 문제이다. 나는 0-1 BFS를 사용하였다.

원래 BFS는 모든 간선의 가중치가 동일한 그래프에서만 사용이 가능하다.

따라서 이럴 때는 다익스트라 알고리즘을 사용해야 한다. 그러나 간선의 가중치가 0와 1의 두 종류일 경우

0-1 BFS를 사용할 수 있다. 이는 가중치가 낮은 (0인) 탐색을 heap을 사용하여 먼저 실행하고 이후에 가중치가 1인 탐색을 실시하는 것이다.

따라서, heap에 넣는 튜플은 (가중치, x좌표, y좌표)가 되어야 한다.

 

 

 

---

• 소스코드 : 

import sys
from heapq import heappop,heappush
input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,-1,1]

M,N = map(int,input().split())
board = [list(input().strip()) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]
heap = []
heappush(heap,[0,0,0])
visited[0][0] = 1
while heap:
    wall, x, y = heappop(heap)
    if x == N-1 and y == M-1:
       print(wall)
    for i in range(4):
        ax = x + dx[i]
        ay = y + dy[i]
        if 0 <= ax < N and 0 <= ay < M:
            if board[ax][ay] == '0' and visited[ax][ay] == -1:
                heappush(heap,[wall,ax,ay])
                visited[ax][ay] = 1
            if board[ax][ay] == '1' and visited[ax][ay] == -1:
                heappush(heap,[wall+1,ax,ay])
                visited[ax][ay] = 1