[BOJ][C#] 1446 지름길

LimJaeJun·2023년 12월 15일

algorithm boj

PS/BOJ

목록 보기

68/108

📕 문제

📌 링크

📗 접근 방식

알고리즘 선택
1. 음이 아닌 가중치 및 최단 거리 탐색이라서 다익스트라를 고려해봄.
2. 최소값을 출력하는거라 뭔가 DP로 풀 수 있을 것 같았음.
최종적으로 DP 알고리즘을 선택하여 풀이 시작

DP 풀이

지름길을 저장한 Dictionary 자료 구조 사용
- Key : 출발 지점
- Value : (도착지점, 지름길의 거리)들 (한 출발 지점에서 여러 지름길이 있을 수 있음)
- 지름길 저장시
  - 도착지점 - 출발점이 지름길의 거리보다 작거나 같으면 저장하지 않음 (그냥 가는게 더 가까움)
  - 목적지(d)보다 더 멀리 가는 경우 저장하지 않음 (역주행할 수 없다)
dp배열 선언
- dp[i] = i키로까지 주행시 이동할 수 있는 최소 주행 거리
- 초기값을 dp[i] = i로 설정 (지름길이 없을 경우 그냥 가는 것이 최선)
0부터 목적지(d)까지 탐색
- 이전(i-1)까지 갈 수 있는 최소거리 + 1과 dp[i]중에 최소값을 저장
- 지름길이 없다면 다음으로 이동
- 지름길이 있다면
  - 해당 딕셔너리에 저장된 키에 해당하는 리스트를 가져와 탐색
  - 지름길의 출구 최소 거리가 기존 최소 거리보다 작을 경우 최신화
최종 목적지까지 가는 최소 거리인 dp[d]를 출력

📘 코드

namespace BOJ_1446
{
    class Program
    {        
        static void Main()
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            int[] inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            int n = inputs[0];
            int d = inputs[1];

            Dictionary<int, List<(int, int)>> dict = new Dictionary<int, List<(int, int)>>(); // Key : 출발지점 Value : 도착지점, 지름길 거리
            
            for (int i = 0; i < n; i++)
            {
                inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
                
                // 그냥 거리가 더 짧은 경우
                if (inputs[1] - inputs[0] <= inputs[2]) continue;
                // 목적지보다 더 멀리 가는 경우 (역주행할 수 없다)
                if (inputs[1] > d) continue;
                
                dict.TryAdd(inputs[0], new List<(int, int)>());

                dict[inputs[0]].Add((inputs[1], inputs[2]));
            }

            // dp[i] i키로까지 주행시 이동할 수 있는 최소 주행 거리
            int[] dp = new int[d + 1];

            // 지름길을 가지 않고 갈 수 있는 방식으로 초기화
            for (int i = 0; i <= d; i++)
            {
                dp[i] = i;
            }
            
            for (int i = 0; i <= d; i++)
            {
                // i-1까지 올 수 있는 최소거리 (0인경우는 -1 인덱스를 참조할 수 없기 때문에 삼항연산자로 예외처리
                int beforeDist = i == 0 ? -1 : dp[i - 1];
                
                // i-1까지 올 수 있는 최소거리 + 1 과 그냥 오는 거리 중 최소값을 저장
                dp[i] = Math.Min(dp[i], (beforeDist + 1));

                // 지름길이 없다면 패스
                if (dict.ContainsKey(i) == false) continue;
                
                // 지름길 탐색
                for (int j = 0; j < dict[i].Count; j++)
                {
                    // 지름길의 출구 최소거리가 기존 최소거리보다 작을 경우 최신화
                    if (dp[dict[i][j].Item1] > dp[i] + dict[i][j].Item2)
                    {
                        dp[dict[i][j].Item1] = dp[i] + dict[i][j].Item2;
                    }
                }
            }
            
            sw.Write(dp[d]);
            
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}