등수 찾기( BOJ 17616 )

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

17616번: 등수 찾기

 

문제 파악하기

N명의 사람 중 주어진 X가 될 수 있는 등수의 범위를 찾는 문제입니다. 등수의 범위라고 하니 뭔가 확률적으로 생각해야 될 것처럼 보이지만 등수의 의미를 생각한다면 그리 어렵지 않게 풀 수 있는 문제입니다.

 

문제 해결하기

그렇다면 등수의 의미는 무엇일까요? 등수란 자신보다 앞에 몇 명이 있으며, 뒤에 몇 명이 있는지를 나타내는 수치입니다. 만약 내 앞에 5명 중 1명의 사람이 있다면 나는 현재 2등이라는 의미이며, 반대로 5명 중 내 뒤에 1명의 사람만 있다면 나는 현재 4등이라는 의미입니다. 그렇기에 우리는 X의 앞에 몇 명이 있으며, 뒤에 몇 명이 있는지에 따라 등수의 범위를 구할 수 있습니다.

 

앞/뒤에 몇 명이 있는지는 주어진 정보를 그래프로 변환하여 탐색하면 구할 수 있습니다. 간선의 비용을 각각 다르게 설정한 다음, DFS/BFS를 활용하면 앞/뒤에 각각 몇 명의 사람이 있는지 구할 수 있습니다. 그리고 우리는 구한 값을 토대로 X가 가질 수 있는 순위의 최솟값과 최댓값을 구할 수 있습니다. 기본적인 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <utility>
#define NMAX 100010
#define PAIR pair<int, int>
using namespace std;
 
int N, M, X;
int A, B;
 
int visited[NMAX];
vector< int > ans;
vector< PAIR > graph[NMAX];
 
int search(int cur, int d) {
    int nxt, nd, cnt=0;
 
    for(PAIR p:graph[cur]) {
        nxt = p.first;
        nd = p.second;
        if(d != nd or visited[nxt]) continue;
 
        visited[nxt] = 1;
        cnt += search(nxt, d)+1;
    }
 
    return cnt;
}
 
int main() {
    scanf("%d %d %d", &N, &M, &X);
    for(int i=1;i<=M;i++) {
        scanf("%d %d", &A, &B);
 
        graph[A].push_back({B, 1});
        graph[B].push_back({A, -1});
    }
 
    // d=-1: X보다 큰 값 개수 / d=1: X보다 작은 값 개수
    for(int d=-1;d<=1;d+=2) {
        memset(visited, 0, sizeof(visited));
 
        visited[X] = 1;
        ans.push_back(search(X, d));
    }
 
    printf("%d %d", ans[0]+1, N-ans[1]);
 
}

후기

순위를 가장한 그래프 문제입니다. 주어진 정보를 그래프로 바꿔서 생각할 수 있는지 물어보는 문제로, 정올 문제답게 생각이 필요한 문제라고 생각합니다. 그래프를 연습하는 사람에게 추천하고 싶은 좋은 문제입니다.