백준 2252번 줄 세우기

문제 링크 : https://www.acmicpc.net/problem/2252

 

문제 요약

N명의 학생들을 키 순서대로 줄을 세우되, 모든 학생들을 다 비교해보는게 아닌 두 명씩 일부 학생들의 키를 비교한다.

입력에서 주어지는 A,B 쌍은 키 순서대로 주어지고, 학생들의 번호는 1부터 N번이다.

 

풀이

위상 정렬 문제입니다.

위상 정렬이란 ? https://suhwanc.tistory.com/74

위상 정렬

위상 정렬은 그래프의 간선 u, v (이 문제에선 a,b 쌍을 말한다) 이 u가 v보다 먼저일 때 정점의 순서를 찾는 알고리즘입니다. 위상 정렬을 구현할 때는 bfs를 사용합니다!

 

 

 

위상 정렬의 결과는 여러가지가 될 수 있는데 문제에서 주어진 예제 입력 2에 대한 위상 정렬 결과는

(4,2,3,1), (3,1,4,2) 가 될 수 있다. 왜냐하면 (4,2),(3,1) 두 그룹간의 키 차이는 구분할 수 없기 때문에

4가 2보다 앞서고, 3이 1보다 앞서면 모두 답이될 수 있다.

 

코드를 먼저 보면서 추가로 설명하자면

 

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ind[32001];
vector<int>v[32001];
int main()
{
    queue<int> q;
    int n, m; scanf("%d %d", &n, &m);
    
    for (int i = 0; i < m; i++) {
        int a, b; scanf("%d %d", &a, &b);
        ind[b] += 1;
        v[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(i);
        }
    }
    vector<int> ans;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for (int i = 0; i < v[x].size(); i++) {
            int y = v[x][i];
            ind[y] -= 1; //한 단계씩 낮추면서
            if (ind[y] == 0) {
                q.push(y);
            }
        }
    }
 
    return 0;
}

 

가장 처음에 나오는 for 반복문에서 그래프를 구현함과 동시에 ind 배열 (차수를 의미합니다) 을 만들어 줍니다.

 

그 다음 나오는 for 반복문은 차수가 0인 노드들을 모드 큐에 넣어준 후 bfs를 구현합니다.

 

bfs에서는 기본적인 bfs와 동일하게 큐에서 노드들을 하나 씩 pop하되,

다른 점은 그 노드와 연결된 노드들의 차수를 1씩 감소시켜준다는 것입니다.

왜냐하면 그 노드들이 이미 큐에 넣어진 노드들과 연결되어 있을 수 있기 때문에

같은 노드들을 중복으로 push하는 상황을 막기 위해 계속 1씩 감소시킵니다.

 

이런 과정으로 ans vector에 결과를 저장해주면 위상 정렬의 결과가 ans에 형성됩니다.

결과는 큐의 초기값의 순서에 따라 달라질 수 있지만 모두 정답이 됩니다.

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~