[Python] 백준 1261번 알고스팟

문제

1261번: 알고스팟

입력 

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

출력 

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

입력 예제

3 3
011
111
110

4 2
0001
1000

6 6
001111
010000
001111
110001
011010
100010

출력 예제

3

0

2

문제 풀이 (BFS)

• 벽을 깨는 횟수를 저장하는 리스트를 만들어 벽을 깰 때마다 카운트
• 벽을 최소한으로 깨야하므로, 벽이 없는 경우를 우선적으로 삽입한다 -> appendleft
• 벽이 있는 경우 뒤에 삽입
• 최종적으로 깬 벽의 횟수 출력

코드

from collections import deque
n, m = map(int,input().split())
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
wall = [[-1] * n for _ in range(m)]
graph = []
for _ in range(m):
    graph.append(list(map(int,input())))

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    wall[y][x] = 0

    while queue:
        y, x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < m and 0 <= nx < n:
                if wall[ny][nx] == -1:
                    if graph[ny][nx] == 0:
                        wall[ny][nx] = wall[y][x]
                        queue.appendleft((ny, nx))
                    elif graph[ny][nx] == 1:
                        wall[ny][nx] = wall[y][x] + 1
                        queue.append((ny, nx))
bfs(0,0)
print(wall[m - 1][n - 1])

문제 풀이(Dijkstra)

• 0과 1을 거리의 비용으로 생각하고 다익스트라 알고리즘 수행
• [m][n]번째 인덱스에 저장되어있는 벽을 깨는 최소 횟수 출력

코드

import heapq
n, m = map(int,input().split())
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
INF = int(1e9)
distance = [[INF] * n for _ in range(m)]
graph = []
for _ in range(m):
    graph.append(list(map(int,input())))

def dijkstra():
    q = []
    # (거리, 세로, 가로)
    heapq.heappush(q,(0,0,0))
    distance[0][0] = 0

    while q:
        dist, y, x = heapq.heappop(q)
        if distance[y][x] < dist:
            continue

        # 상하좌우 이동
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 탐색하려는 거리가 맵의 범위를 벗어날 경우 무시
            if 0 > ny or 0 > nx or ny >= m or nx >= n:
                continue
            # 탐색한 곳의 최단경로 갱신
            cost = dist + graph[ny][nx]
            if cost < distance[ny][nx]:
                distance[ny][nx] = cost
                heapq.heappush(q,(cost, ny, nx))

dijkstra()
print(distance[m - 1][n - 1])