백준(BOJ) 17616 등수 찾기 C++ 풀이

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

17616번: 등수 찾기

풀이에 이용된 알고리즘: DFS, BFS

 

주어진 테스트 케이스보다 풀이자가 다소 확장된 테스트 케이스를 만들어서 도출해보는 것을 추천한다.

 

9 7 4
1 3
2 3
3 4
3 7
4 6
5 8
7 9

 

본인은 위 테스트 케이스를 제작 및 이용했다. 4번이 몇 등인지 최고 등수(숫자가 작을 수록 최고라고 표현하겠다.)와 최저 등수(= 최악의 등수)를 찾는 것이다.

 

그래프를 직접 그려보면 5번과 8번은 완전히 다른 그룹이므로 아예 고려하지 않아도 되고, 4번보다 확실하게 앞에 있거나 뒤에 있는 번호들 외에 4번과의 등수 관계 추론이 불가능한 번호들 (7번, 9번)이 있다.

 

정말 바보 같이 최고, 최저 등수 추론을 위해서 식까지 세우고, 다른 그룹인지를 판단하고자 union-find 개념까지 이용하여 풀이를 했었는데(이렇게 해도 100점이 뜨긴 했다.) 굉장히 간단히 풀이할 수 있다.

 

최고, 최저 등수 파악을 위해서 필요한 것은 확실히 나보다 앞에 있는 사람들의 수와 확실히 내 뒤에 있는 사람들의 수가 필요하다.

 

이는 정방향 간선과 역방향 간선의 정보를 나타내는 인접 리스트를 각각 만들고, 각각에 대해서 변수 x인 4번을 시작점으로 dfs를 적용하면 간단히 파악할 수 있다.

 

코드는 아래와 같다. 나처럼 이상한 고민(?)을 하신 분들이 있을텐데 위 bold체 문장과 하기의 코드를 본다면 조금 허탈할 것 같다고 생각된다.

 

/* BOJ 17616 등수 찾기 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int n, m, x, visited[100001];
vector<int> adj[100001], reverse_adj[100001];
int cnt = -1, reverse_cnt = -1;
 
void dfs(int cur)
{
    if (visited[cur])
        return;
 
    visited[cur] = true;
    cnt++;
 
    for (int next : adj[cur])
        dfs(next);
}
 
void reverse_dfs(int cur)
{
    if (visited[cur])
        return;
 
    visited[cur] = true;
    reverse_cnt++;
 
    for (int next : reverse_adj[cur])
        reverse_dfs(next);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m >> x;
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
 
        adj[a].push_back(b);         // 정방향 간선
        reverse_adj[b].push_back(a); // 역방향 간선
    }
 
    dfs(x);
 
    memset(visited, 0x00, sizeof(visited));
    reverse_dfs(x);
 
    cout << reverse_cnt + 1 << ' ' << n - cnt << endl;
 
    return 0;
}