[BOJ]2025 골랜디

Gold Random Defense

💻250101~250110 (골5~골4)

1. 창영이와 퇴근 (골4) 22116

다익스트라

다익스트라는 INF로 배열을 만든 후 더 작은 값이 있으면 갱신해준다.

visited 필요 없는 이유: height[x][y]가 c보다 작으면 이미 방문을 한 것이므로 height로 방문 여부를 대체 할 수 있다.

A[nx][ny]로 가는 최대 경사를 구한 후 new_cost가 현재 height[nx][ny]보다 작으면 갱신한 후 heap에 넣는다.

2. 시간낭비 (골2) 30464

DP

a[i]이 0이면 같은 공간에 계속 갈 수 있다. 이때 예외처리를 해주어야 한다.

1)앞으로, 2)뒤로, 3)앞으로 가면서 dp 계산을 해주는데 최댓값으로 계속 갱신하면 된다.

3. 최소비용 구하기 (골5) 1916

다익스트라

전형적인 다익스트라 문제이다.

answer에는 누적된 값이 들어가기 때무에 INF를 100,000이 아니라 매우 큰 수로 초기화해야 한다.

최소 힙에 (가중치, 출발지)을 넣는다. 이미 최솟값이면 연산을 건너뛴다. 아니라면 graph에서 도착지를 찾아 갱신 해준 후 힙에 넣는다.

4. 백도어 (골5) 17396

다익스트라

A[i]가 0인 곳만 갈 수 있으므로 26, 27번째 줄을 추가해준다.

나머지는 다익스트라 코드와 동일

4. 미로만들기 (골4) 2665

다익스트라

검정을 만나면 가중치를 +1 해준다.

가중치가 현재 값보다 작으면 갱신한 후 힙에 추가한다.