[BOJ/Gold 5] 백준 31476 :blob_twintail_thinking:(C++)

문제 링크

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

31476번: :blob_twintail_thinking:

 

문제

블롭들은 늘 새로움을 추구해 왔다. 이번에도 블롭들은 새로운 느낌을 원하였고, 이에 블롭들은 매일매일 하늘에 기도하게 된다.

이 기도를 들은 토카는 블롭들에게 양갈래 머리를 하사하였으며, 블롭들은 대 양갈래 시대를 맞게 된다.

 

양갈래 블롭

 

그러나, 일부 블롭들은 거기서 더 새로운 헤어 스타일을 추구하였고, 이들은 그들의 머리를 묶어 포니테일 블롭이 된다.

 

포니테일 블롭의 등장에 슬퍼하는 양갈래 블롭들

처음에는 이상한 블롭 취급을 하며 넘길 수 있는 수준이었지만, 그 수가 점차 하나둘씩 늘어나더니 어느덧 그 수는 양갈래 블롭들과 비슷한 상태가 되었다.

양갈래 블롭들과 포니테일 블롭들은 서로를 싫어하는 감정이 격화되어 결국 '머릿결 전쟁'이 발발하게 된다!

블롭들은 평화를 좋아했기 때문에, 유혈이 낭자하는 전쟁보다는 서로 겨루어 합을 보는 전쟁을 치르기로 합의했고, 이에 토카는 경기 장소로 '양갈래 굴'을 채택하였다. 양갈래 굴은 한때 블롭들의 핵심적인 채광지였고, 광산업이 활발하던 당시에는 입구에서부터 깊이 D까지 총 2^D - 1개의 방으로 구성된 완전 이진 트리의 형태를 띠고 있었고, i번 방과 ⌊i / 2⌋(2 ≤ i ≤ 2^D − 1)번 방을 잇는 길목이 있었다.

그러나 양갈래 굴은 광산업의 쇠퇴로 사용되지 않은 지 오래되어 길목 N군데가 파손되어 탐색을 위해 지나다닐 수 없게 되었다.

하지만, 전쟁은 치러져야 했었기 때문에 결국 갈 수 없는 방을 제외한 모든 방을 가장 빠르게 탐색하는 세력이 승리하는 것으로 전쟁을 치르기로 하였다.

블롭들은 기본적으로 한 방에서 인접한 다른 방까지 가는 데에 걸리는 시간이 U이며, 양갈래 블롭들과 포니테일 블롭들은 서로 다른 탐색 방법을 채택하였다.

양갈래 블롭들은 분기점에 놓일 때마다 세력을 반으로 나누어 탐색하는 방법을 채택하였다. 세력은 언제든지 나눌 때 충분히 많은 양의 블롭이 있어서 나눌 수 있다. 하지만 한 번 나눌 때마다 나눠진 세력이 한 방에서 인접한 다른 방까지 가는 데에 걸리는 시간도 T만큼 증가하게 된다.

양갈래 블롭들은 동시다발적으로 탐색을 진행하기 때문에, 탐색하는 데에 가장 오래 걸린 팀의 총 탐색 시간을 양갈래 블롭들의 탐색 시간으로 간주한다.

포니테일 블롭들은 다 같이 빠르게 한 곳으로 탐색하는 방법을 채택하였다. 분기점이 나타나면, 왼쪽을 우선시하여 탐색한다. 또한 포니테일 블롭들은 더 이상 탐색할 방이 없다면 위로 돌아간다. 이때도 탐색 시간이  U만큼 소모됨에 유의한다.

각각의 블롭들은 길목을 탐색할 때마다 각각의 탐색 시간만큼 지나고 그 외의 시간은 무시한다. 모든 방을 탐색한 즉시 탐색이 끝나게 된다.

이해를 돕기 위해 아래 예제를 준비하였다. 왼쪽이 양갈래 블롭들이 탐색하는 방법, 오른쪽이 포니테일 블롭들이 탐색하는 방법이다.

 

그렇게 전쟁이 선포되고 탐색이 시작되었다! 이 전쟁에서 어느 세력이 승리할지 구해보도록 하자.

 

입력

첫째 줄에는 양갈래 굴의 방 중 가장 깊은 곳의 깊이 D(1 ≤ D ≤ 12)와 파손된 길목의 수 N(0 ≤ N ≤ 2^D − 2), 각 블롭 세력이 기본적으로 탐색하는 시간인 U(1 ≤ U ≤ 100)와 양갈래 블롭들이 갈라졌을 때 추가로 걸리는 시간 T(U < T ≤ 150)가 공백을 사이에 두고 주어진다.

 D, N, U, T 는 모두 정수임이 보장된다.

둘째 줄부터 N개의 줄에 걸쳐 파손된 길목의 시작 점과 끝점을 의미하는 s, e(1 ≤ s < e ≤ 2^D − 1)가 공백을 두고 주어진다. N개의 파손된 길목들에는 같은 길목이 두 번 이상 등장하지 않는다.

 

출력

양갈래 블롭의 탐색이 더 빠르다면 :blob_twintail_aww:를 출력하고, 포니테일 블롭의 탐색이 더 빨랐다면 :blob_twintail_sad:를 출력한다.

만약 두 블롭이 동시에 탐색을 완료하게 된다면, :blob_twintail_thinking:을 출력한다.

 

예제 입력 1

3 1 2 3
1 2

예제 출력 1

:blob_twintail_aww:

예제 입력 2

4 3 1 4
2 5
3 7
6 12

예제 출력 2

:blob_twintail_sad:

예제 입력 3

1 0 1 2

예제 출력 3

:blob_twintail_thinking:

 

알고리즘 분류

• 구현
• 그래프 탐색

 

풀이

양갈래 블롭은 BFS를, 포니테일 블롭은 DFS를 사용하면 된다.

양갈래 블롭들이 탐색한 방의 개수를 세고, 포니테일 블롭이 방을 탐색할 때마다 개수를 1개씩 줄인다.

개수가 다시 0개가 되면 그 이후부터는 방을 탐색하고 되돌아갈 때마다 U만큼의 시간을 더하는 작업을 수행하지 않는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#define MAX 5000
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int D, N, U, T, S, E, Cnt;
bool Banned[MAX][2];
bool Visited[MAX];
int AnswerT, AnswerP;

void input() {
    cin >> D >> N >> U >> T;
    for (int i = 0; i < N; i++) {
        cin >> S >> E;
        if ((S * 2) == E) {
            Banned[S][0] = true;
        }
        else {
            Banned[S][1] = true;
        }
    }
}

void twiintail() {
    queue<pair<pair<int, int>, pair<int, int> > > Q;
    Visited[1] = true;
    Q.push(make_pair(make_pair(1, 1), make_pair(0, 0)));

    while (!Q.empty()) {
        int NowX = Q.front().first.first;
        int NowD = Q.front().first.second;
        int NowS = Q.front().second.first;
        int NowT = Q.front().second.second;
        Q.pop();

        Cnt++;
        AnswerT = max(AnswerT, NowT);

        if (NowD == D) {
            continue;
        }

        if (!Banned[NowX][0] && !Banned[NowX][1]) {
            Q.push(make_pair(make_pair(NowX * 2, NowD + 1), make_pair(NowS + 1, NowT + U + (T * (NowS + 1)))));
            Q.push(make_pair(make_pair((NowX * 2) + 1, NowD + 1), make_pair(NowS + 1, NowT + U + (T * (NowS + 1)))));
        }
        else if (!Banned[NowX][0] && Banned[NowX][1]) {
            Q.push(make_pair(make_pair(NowX * 2, NowD + 1), make_pair(NowS, NowT + U + (T * NowS))));
        }
        else if (Banned[NowX][0] && !Banned[NowX][1]) {
            Q.push(make_pair(make_pair((NowX * 2) + 1, NowD + 1), make_pair(NowS, NowT + U + (T * NowS))));
        }
    };
}

void ponytail(int Depth, int Now) {
    Cnt--;

    if (Depth == D) {
        return;
    }

    if (!Banned[Now][0] && !Visited[Now * 2]) {
        Visited[Now * 2] = true;
        AnswerP += U;
        ponytail(Depth + 1, Now * 2);
        if (Cnt > 0) {
            AnswerP += U;
        }
    }
    if (!Banned[Now][1] && !Visited[(Now * 2) + 1]) {
        Visited[(Now * 2) + 1] = true;
        AnswerP += U;
        ponytail(Depth + 1, (Now * 2) + 1);
        if (Cnt > 0) {
            AnswerP += U;
        }
    }
}

void settings() {
    twiintail();
    ponytail(1, 1);
}

void find_Answer() {
    if (AnswerT < AnswerP) {
        cout << ":blob_twintail_aww:\n";
    }
    else if (AnswerT > AnswerP) {
        cout << ":blob_twintail_sad:\n";
    }
    else {
        cout << ":blob_twintail_thinking:\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}