[Python/파이썬] 백준 1261번 알고스팟

https://www.acmicpc.net/problem/1261

코드 (BFS)

from collections import deque

m, n = map(int, input().split())
maze = [input() for _ in range(n)]

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

break_num = [[n*m]*m for _ in range(n)]
break_num[0][0] = 0
q = deque([(0, 0)])
while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            cnt = break_num[x][y]+(1 if maze[nx][ny] == '1' else 0)
            if break_num[nx][ny] > cnt:
                break_num[nx][ny] = cnt
                q.append((nx, ny))

print(break_num[n-1][m-1])

 

`break_num` : break_num[i][j]는 (i, j)칸까지 가기 위해 부셔야 하는 최소 벽의 개수를 저장할 것이다.

만약 BFS 탐색을 하다가 다음에 이동할 칸 (nx, ny)에 해당되는 `break_num[nx][ny]`보다 현재 칸 (x, y)에서 이동해서 갈 때 더 적게 부시면서 도달할 수 있다면 break_num[nx][ny]를 현재 칸에서 이동할 때 부시게 되는 벽의 개수인 `break_num[x][y]+(1 if maze[nx][ny] == '1' else 0)`로 바꾸어준다. 

 

이렇게 (0, 0)부터 (n-1, m-1)까지 모든 경우의 수를 구해본 뒤에 `break_num[n-1][m-1]`에 저장되어 있는 값이 문제의 답이다.

 

이 문제에서는 (n-1, m-1)에 먼저 도달한다고 그것이 최소로 벽을 부시고 갈 수 있는 경우의 수라는 보장이 없기 때문에 `q.popleft()`한 값이 `x==n-1 and y==m-1` 조건을 달성하더라도 반복문을 탈출하지는 않는다.

 

 물론 이 문제는 이렇게 풀어도 되지만 q에 같은 값이 들어갈 우려가 있으므로, 효율성을 높여줄 필요가 있다. 그래서 다음과 같이 최단 경로 알고리즘을 이용한 코드로 수정해봤다.

코드 (Dijkstra)

from heapq import heappop, heappush

m, n = map(int, input().split())
maze = [input() for _ in range(n)]

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

break_num = [[n*m]*m for _ in range(n)]
break_num[0][0] = 0
q = []
heappush(q, (0, 0, 0))
while q:
    cnt, x, y = heappop(q)
    if x == n-1 and y == m-1:
        break
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            next_cnt = cnt + (1 if maze[nx][ny] == '1' else 0)
            if break_num[nx][ny] > next_cnt:
                break_num[nx][ny] = next_cnt
                heappush(q, (next_cnt, nx, ny))

print(break_num[n-1][m-1])

 

이렇게 수정하면 q에 들어온 요소들이 선입선출 방식이 아니라 부순 벽이 가장 적은 요소부터 pop이 된다. 그렇기에 x가 n-1, y가 m-1에 도달하면 반복문을 끝내도 된다.