백준1261번 파이썬 문제풀이(알고스팟) - (BFS, 다익스트라 )

---

이 문제는 여태 푼 BFS문제보다는 어려운 문제이다. 이 문제는 크게 2가지를 생각할 수 있어야 한다.

1. 벽을 깬 횟수를 따로 저장해 놓는 리스트를 하나 선언해야 한다. (아래의 코드에서는 dist라고 표현)

2. 입력받은 그래프(방 정보)에서 0을(즉, 연결되어 있는방) 우선적으로 돌도록 큐에 추가할때 따로 appendLeft로 추가를 해주어야 한다는 것이다. 그래야만 0인 방을 우선적으로 돌고 그 후에 1(벽이 있는방)을 돌게 된다.

 

아래의 코드에 주석을 달아 놓았다.

 

from collections import deque

N, M = map(int, input().split())

graph = []

for i in range(M):
    graph.append(list(map(int, input())))

dist = [[-1] * N for _ in range(M)]  # 벽을 깬 횟수를 저장

dx = [1, 0, -1, 0]  # 행이동
dy = [0, 1, 0, -1]  # 열이동


def bfs(a, b):
    queue = deque()
    queue.append([a, b]) #초기 0,0 값을 큐에 넣는다.
    dist[0][0] = 0  # 첫번째 벽을 깬 횟수는 0으로 초기화

    while queue:
        x, y = queue.popleft() #큐에 있는 값을 왼쪽부터 뺀다.
        for i in range(4):
            nx = x + dx[i]  # 행 이동
            ny = y + dy[i]  # 열 이동

            if nx < 0 or nx >= M or ny < 0 or ny >= N:  # 범위를 벗어나면 아래의 코드를 실행하지 않는다.
                continue

            if dist[nx][ny] == -1:  # 아직 해당 방을 방문하지 않았다면
                # 만약 벽이 없다면
                if graph[nx][ny] == 0:
                    dist[nx][ny] = dist[x][y]  # 전의 벽을 깬 횟수 그대로 전달해준다.
                    queue.appendleft([nx, ny])  # 벽이 없는 곳을 우선적으로 돌도록 큐의 맨 왼쪽에 넣어준다

                # 만약 벽이 있다면
                else:
                    dist[nx][ny] = dist[x][y] + 1  # 전의 벽을 깬 횟수에서 +1 해준다.
                    queue.append([nx, ny])  # 큐의 맨 오른쪽에 추가


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

 

혹은 위의 개념이 사실상 다익스트라이므로 다익스트라로도 해결할 수 있는 문제이다

import heapq

M, N = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
distance = [[1e10] * M for _ in range(N)]

dr = [-1, 0, 1, 0]  # 상 우 하 좌
dc = [0, 1, 0, -1]  # 상 우 하 좌


def dijkstra():
    q = []
    heapq.heappush(q, (0, 0, 0))
    distance[0][0] = 0
    while q:
        cost, r, c = heapq.heappop(q)

        if cost > distance[r][c]:
            continue

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M:  # 범위를 벗어나거나 이미 방문했으면 진행x
                continue

            if cost + arr[nr][nc] < distance[nr][nc]:
                distance[nr][nc] = cost + arr[nr][nc]
                heapq.heappush(q, (distance[nr][nc], nr, nc))


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