[백준] 알고스팟 풀이

평범한 DFS, BFS 문제와 다른 문제였습니다.

BFS로 풀게 되면 최단거리는 찾을 수 있으나, 벽을 최소로 부수는 거리는 찾지 못하게 됩니다.
왜냐하면 벽을 부순 횟수를 고려하지 않은 채, queue에 들어가는 순서대로 순회하기 때문입니다.

이 문제를 해결하기 위하여 벽을 최소로 부수며 가는 최단거리를 찾기 위하여 해당 좌표값이 1인 경우엔 append로 큐의 맨 뒤에 넣고,
0인 경우엔 appendleft로 1인 지점들보다 먼저 꺼내게 하였습니다. 그렇게 되면 0인 지점들 기준으로 먼저 순회하게 됩니다.

이 외에도 heapq를 이용한 풀이 등도 있으나 원리는 비슷하다고 생각됩니다.

최단 거리 알고리즘에 대해서 공부를 더 해봐야 겠습니다.

from collections import deque


def BFS(x, y, ct):
    queue = deque()
    queue.append([x, y, ct])

    while queue:

        a = queue.popleft()
        if a[0] == N - 1 and a[1] == M - 1:
            print(a[2])
            return

        for i in range(4):
            dx = a[0] + nx[i]
            dy = a[1] + ny[i]

            if dx < 0 or dx >= N or dy < 0 or dy >= M:
                continue

            if visited[dx][dy] == 0:
                visited[dx][dy] = 1

                if arr[dx][dy] == '1':
                    queue.append([dx, dy, a[2] + 1])

                else:
                    queue.appendleft([dx, dy, a[2]])


M, N = map(int, input().split())
arr = []
visited = [[0 for i in range(M)] for j in range(N)]
total = []
nx = [-1, 0, 1, 0]
ny = [0, -1, 0, 1]

for i in range(N):
    arr.append(input())

BFS(0, 0, 0)

추가로 heapq를 이용한 풀이도 공유합니다. heapq의 특성상 앞에 나오는 인덱스 기준으로 오름차순 정렬되기 때문에 벽을 부순 횟수를 기록한 ct 변수가 리스트의 맨 앞에 옵니다.

from collections import deque
import heapq

def BFS(x,y,ct):
    
    heap = []
    heapq.heappush(heap, [ct,x,y])
    
    while heap:
        
        a = heapq.heappop(heap)
        if a[1] == N-1 and a[2] == M-1:
            print(a[0])
            return
            
        for i in range(4):
            dx = a[1] + nx[i]
            dy = a[2] + ny[i]
            
            if dx < 0 or dx >= N or dy < 0 or dy >= M:
                continue
                
            if visited[dx][dy] == 0:
                visited[dx][dy] = 1
                
                if arr[dx][dy] == '1':
                    heapq.heappush(heap, [a[0]+1,dx,dy])
                    
                else:
                    heapq.heappush(heap, [a[0],dx,dy])
    
M,N = map(int, input().split())
arr = []
visited = [[0 for i in range(M)] for j in range(N)]
total = []
nx = [-1,0,1,0]
ny = [0,-1,0,1]

for i in range(N):
    arr.append(input())
    
BFS(0,0,0)