Fine Dining( BOJ 16763 )

문제

16763. Fine Dining : https://www.acmicpc.net/problem/16763

16763번: Fine Dining

 

문제 파악하기

• (n-1)마리의 소들은 각각 1 ~ (N-1)번 초원에 있으며 N번 초원에 있는 헛간으로 돌아오고 있습니다.
• 소들이 돌아오는 길에 건초가 있는 초원에 들렀다 올 수 있는지 없는지 판단하는 문제입니다.
• 건초가 주는 만족감(yumminess)에 따라 초원을 들를 수 있는지 없는지 구분하는게 중요합니다.
• 우선 1 ~ (N-1)까지 모두 N으로 돌아가기 때문에 반대로 생각하는게 알고리즘을 설계하기에 편리합니다.
• 시작점을 N으로 설정하면 한번의 탐색으로 1 ~ (N-1)까지의 최단경로를 구할 수 있습니다.
• 다만, 현재 식사를 했는지 안 했는지가 중요하기 때문에 단순한 다익스트라 알고리즘으로는 문제를 풀 수 없습니다.

 

문제 해결하기

• 그렇다면 식사를 했는지 안 했는지까지 기록하도록 2차원 배열을 사용하여 다익스트라 알고리즘을 설계하면 됩니다.
• dist[i][0]은 현재 i번 초원까지 식사를 안 했을 경우의 최단 경로를 의미하며,
  dist[i][1]은 현재 i번 초원까지 식사를 하고 왔을 경우의 최단 경로를 의미합니다.
• 여기서 중요한 점은 건초를 먹을 때엔 지금까지의 시간에서 만족감(yumminess)만큼을 줄여줘야 한다는 점입니다.
• 만족감(yumminess) 만큼의 시간을 빼준 상태에서 다익스트라 알고리즘을 사용하면 모든 경우의 최단 경로를 얻을 수 있습니다.
• 마지막으로 dist[i][0] < dist[i][1] 인지 아닌지 출력해주면 됩니다.

 

후기

다익스트라 알고리즘의 응용 문제라고 생각합니다. 다만, 2차원 배열을 활용한 다익스트라 알고리즘 문제는 자주 나오기 때문에 익혀둘 필요가 있는 문제 유형이라고 생각합니다.