백준 16156 : 장애물 달리기

https://www.acmicpc.net/problem/16156

16156번: 장애물 달리기

 

해결 방법 : 다익스트라

• 모든 목적지에서 출발지로 역방향 탐색하였다.
  • 출발지 -> 목적지로의 모든 탐색 시, 최종 cost를 알 수 없기 때문에 모든 board를 탐색해야 하므로 시간 초과에 걸린다. (또는 메모제이션 같은 기법을 적용해야 할 것이다.)
• 목적지에서 탐색을 할 때, 해당 목적지의 row를 담은 변수 goal을 다음 노드에 계속 넘겨준다.
  • 우선순위큐에서 pop된 노드의 column이 0이고 당시의 cost가 최소일 때, 해당 노드의 row에서 출발한 사람이 도착할 목적지가 바로 goal일 것이다.

 

<의문점>

문제에 따르면 출발 당시에 서있는 board의 cost는 비용에 합산되지 않는다.

따라서, 목적지부터 역으로 출발한 노드가 출발선(col = 0인 노드)에 도착하는 순간에는 해당 cost(board[Xn][0])은 전체 cost에 합산하지 않아야 한다. (물론 해당 cost를 합산 해도, 결국 해당 출발점을 탐색하는 순간이 올 것이고, 결과값도 잘 나올 것이다. )

따라서, 출발 당시 cost를 미포함하는 코드를 구현해 보았는데 중간에 오답 처리가 된다...

(물론 출발점은 아니지만, 출발 이후 출발선상을 이동할 때는 cost에 합산하도록 했음.)

해당 코드는 주석 처리 해두었는데 왜 오답 처리가 되는지 정말로 모르겠다...

혹시 반례를 아시는분이 있다면 답글로 남겨주시길 바랍니다...ㅠㅠ

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

def solution(N, M, board):
    answer = [0] * N 
    D = [(1,0), (-1,0), (0,1), (0,-1)]

    dist = [[float('inf')] * M for _ in range(N)]
    Q = []
    for n in range(N): # 목적지들 heapq에 push
        heappush(Q, (board[n][M-1], n, M-1, n))
        dist[n][M-1] = board[n][M-1]

    while Q: # 다익스트라
        cd, cr, cc, goal = heappop(Q) # current dist(cost), row, col, 목적지
    
        if dist[cr][cc] < cd: continue
        if cc == 0: # 목적지 -> 출발선에 도착
            answer[goal] += 1 # 해당 목적지 ++
            # cd += board[cr][cc] # 출발선이 경로에 있는 경우를 고려, 출발지 cost 합산

        for d in D: # 4방향 탐색
            nr, nc = cr + d[0], cc + d[1]
            if (0 <= nr < N) and (0 <= nc < M): # board 내부이면,
                nd = cd + board[nr][nc] # 이동을 위한 new cost
                # if nc == 0: # 처음 출발에는 cost가 소요되지 않음 
                    # nd -= board[nr][nc]
                if nd < dist[nr][nc]: # 최소 비용 갱신
                    dist[nr][nc] = nd
                    heappush(Q, (nd, nr, nc, goal))

    return answer

if __name__ == '__main__':
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    result = solution(N, M, board)
    for n in range(N):
        print(result[n])