[백준][BFS][다익스트라] 1261. 알고스팟

알고스팟

1261번: 알고스팟

 

• 풀이
  • ⚠️이전에 도착한 거리와 지금 온 거리를 비교하려고 했더니 방문처리가 불가능한 문제에 직면!
    • 벽을 부수는 최소 횟수이므로 벽을 최대한 안 부수는 곳으로 먼저 이동해야
    • 한번 이동한 곳을 다시 가지 않으면서 최솟값을 가질 수 있다
  • 벽이 없는 경우를 appendleft 로 먼저 확인하게 함
    • → heapq를 쓰면 되는 방식ㅎ

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

distance = [[-1 for _ in range(m)] for _ in range(n)]


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    distance[i][j] = 0

    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if distance[nx][ny] != -1:
                continue
            if graph[nx][ny] == 0:
                distance[nx][ny] = distance[x][y]
                queue.appendleft((nx, ny))
            else:
                distance[nx][ny] = distance[x][y]+1
                queue.append((nx, ny))


bfs(0, 0)
print(distance[n-1][m-1])

 

 

• 다른 풀이
  • 다익스트라

import heapq

m, n = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

distance = [[int(1e9) for _ in range(m)] for _ in range(n)]

def dijkstra():
    queue = []
    heapq.heappush(queue, (0, 0, 0))
    distance[0][0] = 0

    while queue:
        cost, x, y = heapq.heappop(queue)

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if cost+graph[nx][ny] < distance[nx][ny]:
                distance[nx][ny] = cost+graph[nx][ny]
                heapq.heappush(queue, (distance[nx][ny], nx, ny))


dijkstra()
print(distance[n-1][m-1])