[백준1261&파이썬] 가중치가 0과1뿐일때는 다익스트라 또는 0-1BFS를 활용할 수 있다.

# 문제

백준 1261 알고스팟 파이썬 풀이

1261번: 알고스팟

# 코드

'''
  - (1,1) -> (M,N) 으로 이동해야함
  - 무조건 아래랑 오른쪽으로 가는것만 사용해야 하는거 아님?
    - 벽을 최소개로 부수는거지, 최단으로 이동하는 문제는 아닌거 같다
  - 이문제는 0,1(BFS) 가중치 문제로 풀어볼 수 있겠다.
  - 벽을 최소한으로 부수는거이기 때문에 벽을 부수는데 가중치를 1로 두자
  - 0-1bfs와 다익스트라로 풀 수 있을것 같다.
'''

import sys
import heapq
from collections import deque


M, N = map(int, sys.stdin.readline().split())  # M: col, N : row

board = list()

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

for _ in range(N):
  line = list(map(int, sys.stdin.readline().strip()))
  board.append(line)

###### ---  0-1 BFS 풀이 --- ######
# 탐색기준은 벽을 적게 부수는 순위

distance = [ [0] * M for _ in range(N)]
visit = [ [False] * M for _ in range(N)]
visit[0][0] = True

def print2D(arr) :
  for i in range(len(arr)) :
    for j in range(len(arr[i])) :
      print(arr[i][j],end =" ")
    print()
  print()

deque = deque()
deque.append((0,0))

while len(deque) != 0 :
  cur = deque.popleft() # ( row, col )
  # print2D(distance)

  if cur[0] == N - 1 and cur[1] == M - 1:
    print(distance[N - 1][M - 1])
    exit()

  for dir in dirs :
    next = (cur[0] + dir[0], cur[1] + dir[1])
    if 0<= next[0] < N and 0<= next[1] < M and visit[next[0]][next[1]] == False:
      if board[next[0]][next[1]] == 0 :
        deque.appendleft(next)
        visit[next[0]][next[1]] = True
      else :
        deque.append(next)
        visit[next[0]][next[1]] = True
      distance[next[0]][next[1]] += distance[cur[0]][cur[1]] + board[next[0]][next[1]]
###### ---  ------------ --- ######


###### ---  다익스트라 풀이 --- ######
distance = [[float('inf')] * M for _ in range(N)]
distance[0][0] = 0  # 출발지점
heap = list()
heapq.heappush(heap, (0, 0, 0))  # 출발시 가중치, 출발 좌표
target = (N,M)

while len(heap) != 0:
  cur = heapq.heappop(heap) # ( weight, row, col )

  if distance[cur[1]][cur[2]] < cur[0] :
    continue

  for dir in dirs :
    next = (cur[1] + dir[0], cur[2] + dir[1])

    if 0<= next[0] < N and 0<= next[1] < M : # 범위 안이라면
      cost = distance[cur[1]][cur[2]] + board[next[0]][next[1]]

      if cost < distance[next[0]][next[1]] :
        distance[next[0]][next[1]] = cost
        heapq.heappush(heap,(cost,next[0],next[1]))

print(distance[N-1][M-1])
###### ---  ------------ --- ######

 

# 풀이

출처 : https://chan9.tistory.com/120

• 해당 문제는 다익스트라와 0-1BFS를 통해서 문제를 풀 수 있다.
• 처음에는 최단거리로 이동할때, 최소한의 벽만 부수는건줄 알고, 이동을 오른쪽, 아래로만 해야하나 고민했었다. 그런데 그렇게 푸는 것이 아니다.
• 다익스트라의 시간 복잡도는 O( E log E ) 또는 O( E log V ), BFS는 O(V+E)이다.

## 다익스트라

• 문제의 조건은 최단거리로 이동하는 동안 가장 벽을 적게 부수는 것이 아닌, 그냥 목표지점까지 이동하되 벽을 가장 적게 부수는 행위이다. 
• 그렇기 때문에 벽을 부수는 가중치가 1이라고 생각하고, 목표지점까지 가장 적은 가중치로 이동하면 된다.
• 그렇기 때문에 문제에서 생각하지 못했던 가중치가 생기고, 가중치를 최소하는 목표지점까지 이동하는 것이기 때문에 다익스트라를 이용하면 쉽게 풀 수 있다.
• 지금까지 연결리스트로 문제를 풀었지만, 인접행렬로 board를 관리할 수 있었다. 

 

## 0-1BFS

• deque의 appendleft를 활용한다면 문제를 쉽게 해결 할 수 있다.
• 일반적인 bfs에서 4방향에 대한 탐색을 하나의 틱이라고 생각한다면, 해당 틱이 돌면 거리가 +1 증가한다. 그리고 이걸 기준으로 최단 거리를 탐색하게 된다.
• 0-1 BFS에서는 4방향에 대한 탐색을 한다. 그리고 하나씩 뽑아 쓰면 일단 가중치에 대한 틱에서 돌고있다가, 0인 가중치는 공짜로 이동할 수 있기 때문에 deque에 맨앞에 추가한다. 

 

# 참고

아래 블로그에서 0-1BFS를 시각화하여 잘 설명해주신다.

0-1 BFS