[백준/BOJ] gold4 - 1261번 알고스팟 (Python)

▶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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

728x90

▶풀이

bfs를 조금만 더 활용하면 충분히 풀 수 있는 문제이다.

queue에 넣어줄 때 i, j 뿐만 아니라 부숴야 하는 벽의 개수도 함께 넣어주었다.

visit에 부숴야 하는 벽의 개수를 기록해도 되고, queue에 넣어주어도 된다.

 

단 벽을 부숴도 되지 않는 곳으로 가면 appendleft를 해주고,

벽을 부숴야 하는 곳으로 가게 된다면 append를 해주었다.

 

벽을 최소로 부숴야 하기에 이렇게 처리해 주었다.

최소로 되는 부분을 계속해서 이동하기 위해서이다.

 

마지막 칸에 도착하게 되면 바로 cnt 값을 return 해주었다.

from collections import deque


def bfs():
    queue = deque()
    queue.append((0, 0, 0))
    visit[0][0] = 1

    while queue:
        x, y, cnt = queue.popleft()
        if x + 1 == n and y + 1 == m:
            return cnt
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                if arr[nx][ny] == 0:
                    queue.appendleft((nx, ny, cnt))
                else:
                    queue.append((nx, ny, cnt + 1))


m, n = map(int, input().split())
arr = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visit = [[0 for _ in range(m)] for _ in range(n)]

for _ in range(n):
    arr.append(list(map(int, input())))

print(bfs())