[백준 31997번] 즐거운 회의

문제 링크

https://www.acmicpc.net/problem/31997

 

문제 요약

N명의 사람들이 T시간 동안 진행되는 회의에 참석하고 떠나는 시간이 주어진다. 그리고 각 사람들은 서로 친구 관계를 맺고 있다. 회의가 진행되는 동안 특정 시각 t에서 회의에 참석한 사람들 중 친구인 쌍이 몇 쌍인지 계산하는 문제이다..

 

문제 풀이

입력 데이터 처리

N명의 사람들이 언제 도착하고 떠나는지, 그리고 누구와 친구 관계를 맺고 있는지 저장해야 한다. 각 시간마다 어떤 사람이 회의에 참석하고 떠나는지를 기록하면, 회의가 진행되는 모든 시간 동안 현재 참석하고 있는 사람들을 쉽게 파악할 수 있다. 또한, 친구 관계는 인접 리스트를 이용해 저장한다.

// 각 시간대별로 회의에 참석하는 사람을 저장할 벡터
vector<vector<int>> in(t + 1);

// 각 시간대별로 회의에서 떠나는 사람을 저장할 벡터
vector<vector<int>> out(t + 1);

// 각 사람의 친구 관계를 저장할 인접 리스트
vector<vector<int>> friends(n + 1);

// 각 사람의 도착 시간과 떠나는 시간을 입력받아 저장
for (int i = 1; i <= n; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    in[a].push_back(i);  // 도착 시간에 사람 추가
    out[b].push_back(i); // 떠나는 시간에 사람 추가
}

// 친구 관계를 입력받아 인접 리스트에 저장
while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    friends[u].push_back(v); // u의 친구 목록에 v 추가
    friends[v].push_back(u); // v의 친구 목록에 u 추가
}

 

회의 시작부터 종료까지 시뮬레이션

회의에서 떠나고 참석하는 사람들의 정보가 시간별로 저장되어 있어, 회의가 진행되는 상황을 시뮬레이션할 수 있다. 떠나는 사람과 참석하는 사람들의 리스트를 이용해 현재 어떤 사람들이 회의에 참석하고 있는지 시뮬레이션하는 것은 어렵지 않지만, 몇 쌍의 친구가 있는지 관리하는 것은 조금 신경을 써야 한다.

 

\(u\)라는 사람이 회의에서 떠날 때를 생각해보자. \(u\)의 친구 목록에서 현재 회의에 참석하고 있는 친구가 있다면 \(u\)가 떠남으로써 친구 쌍의 수는 그 수만큼 감소하게 된다. 반대로 \(u\)라는 사람이 회의에 참석하게 되면, \(u\)의 친구 목록에서 현재 회의에 참석하고 있는 친구의 수만큼 친구 쌍의 수는 증가한다.

 

이 점을 이용하면 현재 몇 쌍의 친구들이 회의에 참석하고 있는지 효율적으로 계산할 수 있다. 현재 회의에 참석하고 있는 사람들은 boolean 배열을 이용해 쉽게 관리할 수 있다.

// 현재 회의에 참석 중인 사람을 표시하는 배열
vector<bool> joined(n + 1, false);

// 현재 회의에 존재하는 친구 쌍의 수
int total_relations = 0;

for (int i = 0; i < t; ++i) {
    // 회의에서 떠나는 사람들을 시뮬레이션
    for (auto u : out[i]) {
        joined[u] = false;
        
        // u의 친구 목록들 중 현재 회의에 참석 중인 친구가 있다면 친구 쌍의 수를 감소
        for (auto v : friends[u]) {
            if (joined[v]) {
                --total_relations;
            }
        }
    }
    
    // 회의에 참석하는 사람들을 시뮬레이션
    for (auto u : in[i]) {
        joined[u] = true;
        
        // u의 친구 목록들 중 현재 회의에 참석 중인 친구가 있다면 친구 쌍의 수를 증가
        for (auto v : friends[u]) {
            if (joined[v]) {
                ++total_relations;
            }
        }
    }
    
    printf("%d\n", total_relations);
}

 

소스 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n, m, t;

int main() {
    scanf("%d%d%d", &n, &m, &t);
    
    // 각 시간대별로 회의에 참석하는 사람을 저장할 벡터
    vector<vector<int>> in(t + 1);
    
    // 각 시간대별로 회의에서 떠나는 사람을 저장할 벡터
    vector<vector<int>> out(t + 1);
    
    // 각 사람의 친구 관계를 저장할 인접 리스트
    vector<vector<int>> friends(n + 1);
    
    for (int i = 1 ; i <= n ; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        in[a].push_back(i);
        out[b].push_back(i);
    }
    
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        friends[u].push_back(v);
        friends[v].push_back(u);
    }
    
    // 현재 회의에 참석 중인 사람을 표시하는 배열
    vector<bool> joined(n + 1, false);

    // 현재 친구 관계 쌍의 총 수
    int total_relations = 0;

    for (int i = 0; i < t; ++i) {
        // 현재 시간에 회의에서 떠나는 사람들 처리
        for (auto u : out[i]) {
            joined[u] = false; // 사람이 회의에서 떠남
            
            // 친구 목록을 순회하며 현재 회의에 참석 중인 친구를 찾음
            for (auto v : friends[u]) {
                if (joined[v]) {
                    --total_relations; // 친구 쌍의 수 감소
                }
            }
        }
        
        // 현재 시간에 회의에 참석하는 사람들 처리
        for (auto u : in[i]) {
            joined[u] = true; // 사람이 회의에 참석
            
            // 친구 목록을 순회하며 현재 회의에 참석 중인 친구를 찾음
            for (auto v : friends[u]) {
                if (joined[v]) {
                    ++total_relations; // 친구 쌍의 수 증가
                }
            }
        }
        
        // 현재 시간에 친구 관계 쌍의 총 수를 출력
        printf("%d\n", total_relations);
    }
}