[Baekjoon Online Judge] 백준 1261번 알고스팟(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1261번 알고스팟

(Python)

(글쓴날 : 2020.06.10)

 

---

* Baekjoon Online Judge, 백준 1261번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1261번 알고스팟

---

1) 문제

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

1261번: 알고스팟

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

벽이 1로 표시된 미로가 주어질 때, (0, 0)에서 (M, N)까지 벽을 최소로 부수면서 가는 횟수를 구하는 문제입니다.

 

저의 경우, 다익스트라를 적용하였고, Python을 사용했습니다.

주어진 2차원 배열 미로에서 배열의 원소를 정점으로, 벽을 가중치로 두어 인접 리스트로 변환한 뒤, 다익스트라를 적용하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
def BFS(hq):
    while(hq):
        wei, vec = heapq.heappop(hq)
 
        if di[vec] > wei:
            di[vec] = wei
 
            for w, v in adjList[vec]:
                heapq.heappush(hq,(w+wei, v))
 
N, M = map(int,input().split())
N, M = M, N
maze = [list(map(int,input().rstrip())) for _ in range(N)]
 
adjList = [[] for _ in range(N*M)]
INF = 2147483647
di = [INF] * (N*M)
di[0] = 0
hq = []
 
index = 0
for i in range(N):
    for j in range(M):
        if i-1 > -1:
            adjList[index].append((maze[i-1][j], index-M))
        if i+1 < N:
            adjList[index].append((maze[i+1][j], index+M))
        if j-1 > -1:
            adjList[index].append((maze[i][j-1], index-1))
        if j+1 < M:
            adjList[index].append((maze[i][j+1], index+1))
        index += 1
 
for w, v in adjList[0]:
    heapq.heappush(hq, (w, v))
 
BFS(hq)
 
print(di[-1])

---