백준: 1261 알고 스팟

문제

1261번: 알고스팟

 

문제 풀이

 주어진 미로에는 2가지의 경우의 수가 존재한다. 첫 번째는 벽이 있는 경우이고, 두 번째는 벽이 없는 경우이다. 문제를 풀기 위해서는 벽을 최소한으로 부수고, [N, M]에 도착하는 경우를 반환하여야 한다. 만약 2개의 가중치가 아닌 여러 가중치가 설정되어 있다면, 다익스트라로 풀어야 한다. 하지만 문제에서는 벽이 없는 경우에 대한 우선순위를 주면 되므로 이전에 푼 숨바꼭질 3과 같이 BFS를 통해서도 풀 수 있다.

 

 아래의 경우의 수를 판단하여 코드를 작성하면 문제를 해결할 수 있다.

 

• 상, 하, 좌, 우로 방문 가능한 경로를 탐색한다.
  • 방문 가능한 경로 중 벽이 없는 경우 (0)이면 `appendleft`로 큐에 추가한다.
  • 이와 반대로 벽이 있는 경우면 `append`로 큐에 추가한다.
  • `deque`에서 값을 꺼낼 때 `popleft`를 통해 꺼내게 되므로 `appendleft`로 우선순위를 줄 수 있다.
• `visited`를 단순히 방문 여부를 체크하지 않고, 벽이 있다면 이전에 부순 벽의 수에 + 1을 해준다.
• 이와 반대로 벽이 없다면, 이전에 부순 벽의 수만 반영한다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < m and 0 <= y < n and graph[x][y] > -1


def bfs(start):
    q = deque([start])

    while q:
        cur_x, cur_y = q.popleft()

        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y

            if visitable(next_x, next_y):
                visited[next_x][next_y] = visited[cur_x][cur_y]

                if not graph[next_x][next_y]:
                    q.appendleft([next_x, next_y])
                else:
                    visited[next_x][next_y] += 1
                    q.append([next_x, next_y])
                graph[next_x][next_y] = -1

    return visited[m - 1][n - 1]


if __name__ == '__main__':
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().rstrip())) for _ in range(m)]
    visited = [[0] * n for _ in range(m)]
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

    graph[0][0] = -1
    print(bfs([0, 0]))