백준 2252: 줄 세우기

Gold III 난이도 문제를 C++로 풀이한 내용입니다. 여러 학생들의 키 순서를 알고 있을 때, 모든 학생들을 키 순서대로 줄 세우는 문제입니다.

문제 소개

• 문제 번호: 2252
• 문제명: 줄 세우기
• 난이도: Gold III
• 사용 언어: C++
• 실행 시간: 24 ms
• 메모리: 3944 KB
• 문제 요약: N명의 학생과 M개의 키 비교 정보가 주어질 때, 모든 학생을 키 순서대로 일렬로 세우는 한 가지 방법을 출력하는 문제입니다. 만약 가능한 경우가 여러 가지라면 그중 하나를 출력하면 됩니다.

접근 방법

이 문제는 학생들 간의 키 비교 정보를 그래프로 표현하고, 그 그래프의 위상 정렬을 통해 해결할 수 있습니다.

• 그래프 모델링: 학생들을 노드로, 키 비교 정보를 간선으로 생각합니다. 만약 A 학생이 B 학생보다 앞에 서야 한다면, A에서 B로 향하는 방향 간선을 추가합니다. 이는 A가 B의 선행 조건임을 나타냅니다.
• 알고리즘 선택: 방향성 그래프에서 노드의 선행 조건 관계를 만족하는 순서를 찾는 문제는 위상 정렬(Topological Sort)을 사용합니다. 위상 정렬은 진입 차수(indegree)가 0인 노드부터 시작하여, 해당 노드를 방문 처리하고 연결된 간선들을 제거하는 방식으로 진행됩니다. Kahn's 알고리즘을 사용하여 구현했습니다.
• 선택 이유: 위상 정렬은 방향성 비순환 그래프(DAG)에서 간선의 방향을 따라 노드를 나열하는 알고리즘으로, 문제의 "키 순서대로 줄 세우기" 조건에 정확히 부합합니다. Kahn's 알고리즘은 큐를 사용하여 구현이 직관적입니다.

풀이 과정

1. 그래프 및 진입 차수 초기화:
   • 학생 수를 N, 비교 정보를 M으로 입력받습니다.
   • 각 학생을 노드로 하는 인접 리스트 adj를 크기 n + 1로 생성합니다.
   • 각 학생의 진입 차수를 저장할 indegree 벡터를 크기 n + 1로 생성하고 모두 0으로 초기화합니다.
2. 간선 정보 입력 및 진입 차수 계산:
   • M개의 키 비교 정보 a, b를 입력받습니다.
   • a 학생이 b 학생보다 앞에 와야 하므로, a에서 b로 가는 방향 간선을 adj[a]에 추가합니다.
   • b 학생의 진입 차수를 1 증가시킵니다 (indegree[b]++).
3. 위상 정렬 (Kahn's 알고리즘):
   • 진입 차수가 0인 모든 학생들을 큐 q에 추가합니다. 이 학생들은 줄의 맨 앞에 올 수 있는 학생들입니다.
   • 큐가 빌 때까지 다음을 반복합니다:
     • 큐의 맨 앞 노드 curr를 꺼냅니다.
     • curr 학생을 결과 리스트에 추가하고 출력합니다.
     • curr 학생에서 나가는 모든 간선(adj[curr]에 있는 next 노드)에 대해:
       • next 노드의 진입 차수를 1 감소시킵니다 (indegree[next]--).
       • 만약 indegree[next]가 0이 되면, next 노드도 이제 방문 가능하므로 큐 q에 추가합니다.
4. 결과 출력: 큐에서 꺼내 순서대로 출력된 학생들은 위상 정렬된 결과이며, 문제에서 요구하는 키 순서대로 줄 세운 결과가 됩니다.

코드 설명

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main(){
    // 표준 입출력 속도 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m; // n: 학생 수, m: 비교 정보 수
    cin >> n >> m; // 학생 수와 비교 정보 수 입력
    
    vector<vector<int>> adj(n + 1);      // 인접 리스트: 각 학생으로부터 앞에 서야 하는 학생들을 저장
    vector<int> indegree(n + 1, 0);      // 각 노드의 진입차수: 현재 학생 앞에 서야 하는 학생 수를 저장
    
    // 간선 입력 및 진입차수 계산
    for(int i = 0; i < m; i++){
        int a, b; // a: 앞에 서야 하는 학생, b: 뒤에 서야 하는 학생
        cin >> a >> b;
        adj[a].push_back(b); // a 학생 뒤에 b 학생이 와야 하므로 a -> b 간선 추가
        indegree[b]++;      // b 학생은 a 학생으로 인해 진입차수가 1 증가
    }
    
    // 위상정렬 (Kahn's 알고리즘)을 위한 큐
    queue<int> q;
    
    // 진입차수가 0인 노드들을 큐에 추가 (가장 앞에 올 수 있는 학생들)
    for(int i = 1; i <= n; i++){
        if(indegree[i] == 0){
            q.push(i); // 진입차수가 0이면 큐에 삽입
        }
    }
    
    // 큐가 빌 때까지 위상정렬 수행
    while(!q.empty()){
        int curr = q.front(); // 큐에서 가장 앞에 있는 학생(진입차수 0인 학생)을 가져옴
        q.pop();              // 큐에서 제거
        cout << curr << " ";  // 현재 학생을 결과에 출력
        
        // 현재 학생(curr)과 연결된 다음 학생들(next)에 대해 처리
        for(int next : adj[curr]){ 
            indegree[next]--; // curr 학생이 처리되었으므로 next 학생의 진입차수를 1 감소
            if(indegree[next] == 0){ // 만약 next 학생의 진입차수가 0이 되면
                q.push(next);       // next 학생도 이제 앞에 올 수 있으므로 큐에 추가
            }
        }
    }
    
    cout << "\n"; // 결과 출력 후 개행
    
    return 0;
}

복잡도 분석

• 시간 복잡도: O(V + E)
  • V는 학생 수(노드 수), E는 키 비교 정보 수(간선 수)입니다.
  • 모든 노드를 큐에 한 번씩 넣고 빼는 데 O(V)가 걸립니다.
  • 모든 간선에 대해 한 번씩 방문하여 진입 차수를 감소시키므로 O(E)가 걸립니다.
  • 따라서 총 시간 복잡도는 O(V + E)입니다.
• 공간 복잡도: O(V + E)
  • 인접 리스트 adj는 최대 O(V + E)의 공간을 차지합니다.
  • indegree 벡터는 O(V)의 공간을 차지합니다.
  • 큐 q는 최악의 경우 O(V)의 공간을 차지합니다.
  • 따라서 총 공간 복잡도는 O(V + E)입니다.

배운 점

이 문제를 풀면서 위상 정렬의 개념과 Kahn's 알고리즘 구현 방법을 익혔습니다. 특히, 진입 차수를 사용하여 노드의 선행 조건을 관리하고, 진입 차수가 0이 되는 노드를 큐에 넣어 순서를 결정하는 방식이 유용하다는 것을 알게 되었습니다. 그래프 문제에서 복잡한 관계를 단순한 간선과 노드로 모델링하는 능력을 향상시킬 수 있었습니다.