목록2026/08/09 (1)

개발자 쿠키

[다익스트라] 프로그래머스 - 경주로 건설 (JAVA)

문제N x N 보드에서 (0, 0)부터 (N-1, N-1)까지 도로를 건설하는 최소 비용을 구합니다.빈 칸 0, 벽 1이며 벽은 지날 수 없습니다직선 도로 1개당 100원코너 1개당 500원 추가접근비용 기준 다익스트라로 접근했습니다. 문제는 같은 칸에 더 싸게 도착해도 그때의 진입 방향이 나쁘면 이후에 500원이 더 붙어 손해가 될 수 있다는 점입니다. 비용만으로는 한 칸의 상태를 대표할 수 없습니다.그래서 dist[n][n][4]로 (좌표, 진입 방향)을 하나의 상태로 관리하고, 출발 지점은 직전 방향이 없으므로 direction = -1로 두었습니다. 마지막에는 도착 칸의 4방향 값 중 최솟값을 고릅니다.핵심 두 줄다익스트라에서 실제로 중요한 부분은 nCost 계산과 그 밑의 갱신 조건문입니다. 특..
Problem Solving/java 2026. 8. 9. 17:46
이전 Prev 1 Next 다음