C# 코딩테스트 강좌, 임계 경로 구하기

문제 설명

주어진 방향 그래프에서 임계 경로를 구하는 문제입니다. 임계 경로는 그래프 내의 노드와 엣지로 표현되며, 가장 긴 경로를 해결하는 문제입니다. 주어진 그래프는 노드의 개수 n과 엣지의 개수 m으로 구성되어 있습니다.

입력 형식

  • 첫 번째 줄에 정수 n과 m이 주어진다.
  • 다음 m줄에 각각 한 쌍의 정수 u와 v가 주어진다. 이는 노드 u에서 노드 v로 가는 엣지를 나타낸다.

출력 형식

가장 긴 경로의 길이를 출력한다.

예제 입력

    6 7
    1 2
    1 3
    2 4
    3 4
    4 5
    5 6
    3 6

예제 출력

4

문제 풀이 과정

이 문제를 해결하기 위해 다음과 같은 방법을 사용할 수 있습니다.

단계 1: 그래프 표현

주어진 방향 그래프를 Adjacency List 형태로 표현합니다. 이를 통해 각 노드에서 이동할 수 있는 노드들을 쉽게 확인할 수 있습니다.

단계 2: 위상 정렬

가장 긴 경로를 구하기 위해서는 그래프의 모든 노드를 한 번씩 방문해야 합니다. 이를 위해 위상 정렬을 활용합니다. 위상 정렬을 통해 모든 노드는 순서대로 방문할 수 있게 됩니다.

단계 3: 최장 경로 계산

위상 정렬이 완료된 후에는 각 노드에 대해 시작 노드부터 해당 노드까지의 최장 경로를 계산합니다. 이때, 최장 경로의 값을 저장할 배열을 사용합니다.

단계 4: 코드 구현

다음은 C#을 사용한 임계 경로 구하기 코드 구현 예시입니다:


using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int n = 6; // 노드의 수
        int m = 7; // 엣지의 수
        List[] graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List();
        }

        // 엣지 정보 입력
        graph[1].Add(2);
        graph[1].Add(3);
        graph[2].Add(4);
        graph[3].Add(4);
        graph[4].Add(5);
        graph[5].Add(6);
        graph[3].Add(6);
        
        // 위상 정렬을 위한 인접 행렬
        int[] inDegree = new int[n + 1];
        foreach (var edges in graph) {
            foreach (var v in edges) {
                inDegree[v]++;
            }
        }

        // 위상 정렬을 위한 큐
        Queue queue = new Queue();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        // 최장 경로 계산
        int[] longest = new int[n + 1];
        while (queue.Count > 0) {
            int u = queue.Dequeue();
            foreach (var v in graph[u]) {
                longest[v] = Math.Max(longest[v], longest[u] + 1);
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.Enqueue(v);
                }
            }
        }

        // 결과 출력
        int maxPath = 0;
        for (int i = 1; i <= n; i++) {
            maxPath = Math.Max(maxPath, longest[i]);
        }
        Console.WriteLine(maxPath);
    }
}

코드 설명

위의 코드는 다음과 같이 작동합니다:

  1. 그래프를 List 자료구조로 표현합니다.
  2. 모든 엣지에 대해 노드의 진입 차수를 계산합니다.
  3. 진입 차수가 0인 노드를 큐에 추가하여 위상 정렬을 수행합니다.
  4. 위상 정렬된 순서대로 각 노드에 대해 최장 경로를 업데이트합니다.
  5. 최종적으로, 가장 긴 경로의 길이를 출력합니다.

결론

임계 경로 구하기 문제는 위상 정렬과 최장 경로 계산을 통해 효율적으로 해결할 수 있습니다. 이 방법은 다양한 경로 최적화 문제에 적용될 수 있으므로, 기초적인 이해와 실습이 중요합니다.

이 글이 C# 코딩 테스트 준비에 도움이 되기를 바랍니다! 추가적인 질문이나 설명이 필요하시면 댓글로 남겨주세요.

작성자: 조광형