[BOJ] 3865 - 학회원

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

BOJ - 학회원

문제 유형: 문자열 처리, bfs, 그래프, 파싱

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 128MB

문제

상근이는 Sogang ACM-ICPC Team의 회장이다. 서강대학교 컴퓨터 학생들은 하나 또는 그 이상의 학회에 소속되어 있다. 상근이는 학생들이 어떤 학회에 소속되어 있는지 조사해보려고 한다.

상근이는 학회원의 정보를 다음과 같이 작성한다. 아래 예시는 sisobus와 weissblume은 icpc의 학회원이라는 뜻이다.

icpc:weissblume,sisobus.

콜론(:)의 앞에는 학회의 이름이 쓰여 있고, 뒤에는 학회원이 주어진다.

어떤 학회는 모든 회원이 다른 학회에 소속되어 있을 수도 잇다. 따라서, 학회원을 적는 곳에 학회의 이름을 적을 수도 있다.

slug:sisobus,minhyeok,icpc,exupery.

icpc에 소속되어 있는 사람은 slug에도 소속되어 있다는 뜻이다. 즉, slug의 학회원은 아래와 같다.

slug:sisobus,minhyeok,weissblume,sisobus,exupery.

이 경우에 sisobus는 두 번 등장한다. 중복되는 사람의 이름을 하나로 줄이게 되면, 아래와 같이 하나로 줄여서 작성할 수 있다.

slug:sisobus,minhyeok,weissblume,exupery.

학회의 회원 정보가 주어졌을 때, 각 학회의 학회원이 몇 명인지 구하는 프로그램을 작성하시오.

상근이가 작성하는 방법에는 학회의 이름이 중첩될 수도 있다. 아래 예시에서 one에 소속된 회원은 abckhw 한 명이다.

one:another.
another:yetanother.
yetanother:abckhw.

 

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 학회의 수 n이 주어진다. n은 100을 넘지 않는 양의 정수이다. 다음 n개 줄에는 각 학회의 학회원 정보가 문제에서 설명한 형식으로 주어진다. 콜론(:) 앞은 학회 이름이고, 그 뒤쪽은 회원의 이름이 콤마(,)로 구분되어져 있다. 각 정보의 마지막에는 마침표(.)가 하나 주어진다.

학회의 이름은 서로 다르다. 학회원 정보에서 주어지는 회원이 학회 이름이 아닌 경우에는 사람의 이름이다.

입력으로 주어지는 학회 정보에서 순환을 이루는 정보는 없다.

각 그룹 또는 사람의 이름은 비어있지 않은 문자열이며, 길이가 1과 15 사이이다. 또, 알파벳 소문자로만 이루어져 있다.

각 학회에 속한, 그룹이나 사람의 수는 1 이상 10 이하이다.

입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

각 테스트 케이스에 대해서, 제일 처음으로 주어지는 학회에 포함되어 있는 회원의 수를 출력한다.

 

풀이

a:b,c,d.의 꼴에서, a를 source, b,c,d를 destination으로 생각하고 유향 그래프를 만들어주면 된다.

그러고 맨 첫 번째 문장의 source부터 bfs를 돌려서, 방문한 노드들 중, 진출차수가 0인 노드의 개수를 구하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    while ((cin >> n) && n != 0) {
        unordered_map<string, vector<string>> adj;
        unordered_map<string, bool> visited;
        string start;
        for (int i = 0; i < n; i++) {
            string str;
            cin >> str;

            int l = 0, r = 0;
            while (str[r] != ':') {
                r++;
            }
            string src = str.substr(0, r - l);
            visited[src] = false;
            if (i == 0) start = src;
            r++;
            l = r;

            while (r < str.size() && str[r] != '.') {
                while (str.size() && str[r] != '.' && str[r] != ',') {
                    r++;
                }
                string dst = str.substr(l, r - l);
                adj[src].emplace_back(dst);
                visited[dst] = false;
                r++;
                l = r;
            }
        }

        queue<string> q;
        q.emplace(start);
        visited[start] = true;

        int ans = 0;
        while (!q.empty()) {
            string curr = q.front();
            q.pop();

            if (adj[curr].size() == 0) ans++;
            for (const auto &next : adj[curr]) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.emplace(next);
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}