[python] 백준 - 1261. 알고스팟

🤔문제 해결

• G4 | 다익스트라(BFS도 가능)

다익스트라 유형으로 되어있지만 BFS도 가능한거 같다.

BFS로 풀 면 길을 찾아 갈 때 0이면 그냥 가고 1이면 +1해서 가면 된다.

 

이 문제는 다익스트라로 풀어봤다.

( 다익스트라와 우선순위큐(힙큐)는 짝꿍 )

 

• 주어진 미로와 같은 크기의 2차원 배열을 만든다. ( 가중치를 업데이트 해줄 배열 )
• 0,0 부터 주변을 탐색하며 방(0)이면 비용을 현재비용으로 넣고, 벽(1)이면 비용을 현재비용 +1해서 업데이트 해준다.
• 업데이트가 된 지점을들 힙큐에 넣고 목적지가 나올 때 까지 위의 과정을 반복한다.

💻소스 코드

import heapq

if __name__ == '__main__':
    N, M = map(int, input().split())  # 문제는 1부터 시작이므로 -1 해줌
    room = [list(map(int, input())) for _ in range(M)]

    # 가중치 2차원 배열
    key = [[float('inf')] * N for _ in range(M)]

    pq = []
    heapq.heappush(pq, (0, 0, 0))
    key[0][0] = 0
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while pq:
        cost, x, y = heapq.heappop(pq)
        if x == M - 1 and y == N - 1:
            print(key[x][y])
            break

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < M and 0 <= ny < N:
                # 다음 갈 곳이 벽이고, 현재 가는 루트의 비용이 더 작다면 고
                if room[nx][ny] == 1 and cost + 1 < key[nx][ny]:
                    heapq.heappush(pq, (cost + 1, nx, ny))
                    key[nx][ny] = cost + 1
                # 다음 갈 곳이 룸이고, 현재 가는 루트의 비용이 더 작다면 고
                elif room[nx][ny] == 0 and cost < key[nx][ny]:
                    heapq.heappush(pq, (cost, nx, ny))
                    key[nx][ny] = cost
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/1261

1261번: 알고스팟