BOJ 17839 - Baba is Rabbit 문제풀이

문제를 읽고 이해하기

원이는 요즘 유행하는 게임을 하고 있다. 이 게임은 is 라는 단어를 이용해 어떤 사물을 다른 사물로 바꿀 수 있다. 규칙은 다음과 같다.

• 게임 시작 시 몇 개의 명령을 설정해놓는다.
  이 때, 모든 명령의 형태는 p is q 의 형태이며, p, q는 사물이다.
• 두 사물 p, q에 대해 p is q 라는 명령은 사물 p를 사물 q로 바꾼다.
  이러한 행위를 명령을 적용한다고 부른다.

어떤 사물 p에 대해 적용할 수 있는 명령이 두 가지 이상이면, 그 중 아무거나 하나 골라서 적용할 수 있다. (아무 명령도 적용하지 않을 수도 있다.) 그리고 어떤 사물 p에 명령을 한 번 이상 적용한 결과로 다시 p가 나오는 경우는 없다.

게임 초기에 설정된 명령들이 주어졌을 때, Baba에 명령을 적용하여 어떤 사물로 만들 수 있는지 구해보자.

입력

첫 줄에 전체 명령의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

이후 N개의 줄에 걸쳐 명령이 주어진다. 각 명령은 p is q의 형태로 주어지며,  p와 q는 첫 글자가 영문 대문자이고, 나머지 글자는 영문 소문자인 길이 10 이내의 문자열이다.

출력

Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물을 사전순으로 출력한다. 단, 적용할 수 있는 명령이 없다면, 아무것도 출력하지 않는다.

재정의와 추상화

굉장히 문제에서 정보가 많이 주어지기 때문에, 머릿속으로 정확하게 정리하는 것이 필요하다. 그렇지 않으면 '틀렸습니다.'를 수도 없이 볼 것이다.. (경험담)

문제에서 말하는 '그 중 아무거나 하나 골라서 적용할 수 있다.'라는 말의 의미를 잘 해석해야 한다. 하나의 p에 대해 여러 q가 들어왔을 때 그 중 하나만 골라서 처리한다는 이야기가 아니라, 각각의 경우의 명령을 모두 처리해야 한다는 뜻이다.

예를 들면, Baba is Rabbit과 Baba is Cat이 들어왔을 때, 둘 중 하나'만' 선택하는 것이 아니라, 전자를 선택했을 때 진행되는 루트와 후자를 선택했을 때 진행되는 루트 각각 처리한다는 의미이다. (문제의 굉장히 불친절한 설명 때문에 이해가 잘 안될 수도 있다..)

이는 DFS/BFS의 원리와 같다. 둘 중에 어느 것을 선택해서 풀어도 상관 없지만, 필자는 DFS로 풀었으니, DFS로 설명하겠다.

예를 들어, 입력으로 아래와 같이 들어왔다고 치자.

1 Baba is Carrot Baba is Cat Cat is Rabbit Carrot is Mouse Rabbit is Mouse

DFS에서 Baba에서 갈 수 있는 노드는 Carrot과 Cat이 있다.

Baba is Carrot부터 가자. 그 다음, Carrot is Mouse이 온다. 따라서 Baba -> Carrot -> Mouse의 루트이므로 현재까지 Baba가 될 수 있는 사물은 Carrot, Mouse이다.

이제 Baba is Cat으로 가자. 그 다음, Cat is Rabbit, Rabbit is Mouse이 온다. 이는 Baba -> Cat -> Rabbit -> Mouse인데, Mouse는 이미 위에서 들렸던 곳이므로, 최종 루트는 Baba -> Cat -> Rabbit이다. 따라서 최종적으로 Baba가 될 수 있는 사물은 Carrot, Mouse, Cat, Rabbit이다.

컨테이너는 string key값으로 value에 접근할 수 있는 unordered_map을 사용하였다.

---

아직 끝난 것이 아니다..! 문제에서 말한

그리고 어떤 사물 p에 명령을 한 번 이상 적용한 결과로 다시 p가 나오는 경우는 없다.

라는 부분을 처리해야 한다.

그래서 나는 첫 번째로, 처음 p와 q를 입력 받을 때 p != q이여야 한다는 조건을 넣었다. 그리고, A -> B, B -> C, C -> A와 같이 돌고 돌아서 A로 돌아오는 경우도 있으므로, dfs 처리 부분에서, p가 한 번 이상 방문했던 곳인 경우 진행하지 않고 return 해버리도록 처리했다.

만약, 방문했던 곳이 아닌 경우, result라는 이름의 벡터 변수에 p의 값을 추가한다. 그리고 dfs 처리가 끝나면, 마지막으로 사전순으로 출력하라고 하였으므로 sort 함수를 통해 사전순 정렬한 후 출력한다.

코드 작성

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

unordered_map<string, vector<string>> um;
unordered_map<string, int> obj;
vector<string> result;

void dfs(string start) {
    if (obj[start] != 0)
        return;

    if (start != "Baba")
        result.push_back(start);

    obj[start] ++;

    for (const auto& target : um[start]) {
        dfs(target);
    }
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    while (n--) {
        string p, q, trash;
        cin >> p;
        cin >> trash;
        cin >> q;

        if (p != q)
            um[p].push_back(q);
    }

    dfs("Baba");
    sort(result.begin(), result.end());

    for (auto & it : result)
        cout << it << '\n';

    return 0;
}