[백준] 1261번 알고스팟 파이썬 코드

코드 1 (0-1 BFS 풀이)

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [input() for _ in range(m)]
visited = [[0]*n for _ in range(m)]

def bfs(): # 가중치가 0 또는 1만 있기 때문에, 0-1 bfs가 떠올랐다.
  queue = deque([(0,0)])
  dx, dy = [1,-1,0,0],[0,0,1,-1] # 이동할 수 있는 경우의 수
  visited[0][0] = 1 # 첫번째 노드 방문기록을 해준다
  while queue:
    popx, popy = queue.popleft()
    if popx == m-1 and popy == n-1: return visited[m-1][n-1] - 1 # 끝에 도달하면 값 반환
    for i in range(4):
      nx = popx + dx[i]
      ny = popy + dy[i]
      if 0<=nx<m and 0<=ny<n and visited[nx][ny] == 0:
        if graph[nx][ny] == '0': # 빈 방일 경우, 우선순위가 높으므로 가장 앞에 넣어준다.
          visited[nx][ny] = visited[popx][popy] # 이전 값과 같게 방문기록을 해준다.
          queue.appendleft((nx,ny))
        elif graph[nx][ny] == '1': # 벽을 부수는 경우, 일반 bfs처럼 처리해준다.
          visited[nx][ny] = visited[popx][popy] + 1 # 벽 하나를 부쉈으므로 이전값 +1을 해준다.
          queue.append((nx,ny))
print(bfs())

 

풀이 2 (다익스트라 알고리즘 풀이)

# 노드의 개수가 최대 10000개이므로, 플로이드 워셜은 비효율적
# 음의 가중치가 존재하지 않으므로 다익스트라 사용 가능

import heapq, sys
input = sys.stdin.readline

m, n = map(int, input().split())
graph = [input() for _ in range(n)]
visited = [[0]*m for _ in range(n)]

def dijkstra():
  queue = [(0,0,0)]
  dx, dy = [1,-1,0,0], [0,0,1,-1]
  while queue:
    next, nowx, nowy = heapq.heappop(queue) # next 값의 순서대로 정렬을 해야한다.
    if nowx == n-1 and nowy == m-1: return next # 종착지에 도달하면 값 반환
    for i in range(4):
      nx = nowx + dx[i]
      ny = nowy + dy[i]
      if 0<=nx<n and 0<=ny<m and not  visited[nx][ny]:
        visited[nx][ny] = 1 # 방문 기록
        if graph[nx][ny] == '1': # 벽을 부수는 경우, next에 1을 더한 값을 heappush해준다.
          heapq.heappush(queue, (next+1, nx,ny))
        elif graph[nx][ny] == '0': # 빈 방일 경우 그대로 heappush해준다. 우선순위가 높아진다.
          heapq.heappush(queue, (next,nx,ny))
print(dijkstra())