백준 1261 python [알고스팟]

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

from collections import deque

# with open ('./data.txt', 'r') as file:
#     lines = file.read().strip().split("\n")

# M=열=X축, N=행=Y축
# M, N = map(int, lines[0].split(" "))
M, N = map(int, input().split(" "))

graph = []
dist = [[-1] * M for _ in range(N)]
moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]

for i in range(N):
    # graph.append(list(map(int, lines[i+1].strip())))
    graph.append(list(map(int, input().strip())))

def bfs(x, y):
    Q = deque()
    Q.append((y, x))
    dist[y][x] = graph[y][x]
    
    while Q:
        nowY, nowX = Q.popleft()
        
        for i in range(4):
            nextX = nowX + moveX[i] # 열
            nextY = nowY + moveY[i] # 행
            
            if(nextX >= M or nextX < 0 or nextY >= N or nextY < 0):
                continue

            # 첫 방문
            if(dist[nextY][nextX] == -1):
                if(graph[nextY][nextX] == 0):
                    dist[nextY][nextX] = dist[nowY][nowX]
                    Q.appendleft((nextY, nextX))
                else:
                    dist[nextY][nextX] = dist[nowY][nowX] + 1
                    Q.append((nextY, nextX))

            else: # 첫 방문이 아닐 때
                # (최단경로 업데이트)
                if(dist[nextY][nextX] > dist[nowY][nowX] + graph[nextY][nextX]):
                    dist[nextY][nextX] = dist[nowY][nowX] + graph[nextY][nextX]

bfs(0, 0)
print(dist[N-1][M-1])

생각

이전에 풀었던 13549 문제에서 약간 변형된 문제였다.

단지 좌표평면 그래프로 바뀐것 뿐이었다.

그래서 상하좌우를 탐색하면서 최단 경로를 업데이트 해주면 되겠다 생각했다.

풀이

0, 1 값을 가진 가중치 그래프와
각 위치별로 벽을 부순 최소 횟수 배열이 필요하다.

다른 BFS와 마찬가지로 배열의 인덱스를 벗어나는지 검사해주고

이동 하려는 곳이 벽이 없다면 부수지 않기 때문에

이전 위치의 벽 부순 횟수를 그대로 삽입해주면 되고

아니라면 이전 위치 값 + 1을 해서 한번 더 부쉈다고 선언해주면 된다.

그리고 이미 방문했더라도 현재 경로가 기존 값보다 더 벽 부순 횟수가 적다면

현재 경로의 값으로 업데이트 해준다. 즉 최단 경로를 업데이트 해주는 것이다.

(풀고나서 다른 사람의 코드를 확인해보니 최단 경로 업데이트는 굳이 필요없는 로직이긴 했다 ㅎㅎ)