[백준 1261] 알고스팟

문제

www.acmicpc.net/problem/1261

1261번: 알고스팟

 

처음 작성한 코드

import sys
import heapq

M, N = map(int, sys.stdin.readline().split())
arr = []
queue = []
result = [sys.maxsize] * (M*N)
direction = [[-1,0], [0,1], [1,0], [0,-1]] #위, 오, 아래, 왼

result[0] = 0
heapq.heappush(queue, [0,0]) # 좌푯값[x,y]

for i in range(N):
    tmp = []
    line = map(int, sys.stdin.readline().rstrip())
    for j in line:
        tmp.append(j)
    arr.append(tmp)

while queue:
    x, y = heapq.heappop(queue)
    for i in direction:
        if 0 <= x+i[0] < N and  0 <= y+i[1] < M:
            new_x = x+i[0]
            new_y = y+i[1]
            if result[new_x * M + new_y] > result[x * M + y] + arr[new_x][new_y]:
                result[new_x * M + new_y] = result[x * M + y] + arr[new_x][new_y]
                heapq.heappush(queue, [new_x, new_y])

print(result[-1])

1. queue에는 인접한(위, 오, 아래, 왼) 좌표값들이 들어간다. 물론 최단 거리가 변경될 때에만 들어간다.
2. result에는 그 좌표까지의 최단 거리가 들어간다. 2차원 배열을 어떻게 선언하는지 잘 몰라서 1차원 배열로 했고 (0,0)은 [0]으로 접근, (0,1)은 [1]로 접근, (1,0) 은 [1*M+0] 이런식으로 접근했다.
3. 벽이 1이고 방이 0이라고 했으니까 벽을 부시고 방을 들어가면 벽 부신 횟수가 +1 이 되니까 그냥 좌표를 더해주면 된다. 그럼 빈방이면 +0, 벽이면 +1이 되기 때문이다.

 

깨달은 점

• 가중치 있는 그래프에서 최단 거리를 구하라고 할 때 다익스트라 알고리즘을 사용하면 될 것 같다.