[BOJ/Gold 5] 백준 31423 신촌 통폐합 계획(C++)

문제 링크

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

 

문제

극단적인 출산율 감소로 인해 신촌 지역 N개 대학교가 하나의 학교로 통합되었다.

기나긴 회의 끝에, 통합된 학교의 이름은 N개 대학교의 이름을 이어 붙여서 정해졌다. 회의에서 통합된 학교의 이름을 정한 방법은 다음과 같다.

 N개 대학교의 이름 s1, s2, ⋯, sN을 일렬로 나열한다. 이후 다음의 과정을 N − 1번 반복한다.

1.  si, sj가 빈 문자열이 아닌 서로 다른 두 정수 i, j를 고른다.
2.  si의 뒤쪽에 sj를 이어 붙인다.
3.  sj를 빈 문자열로 바꾼다.

모든 과정이 끝난 뒤에는 빈 문자열이 아닌 sk가 하나 남게 되며, 이때 sk가 통합된 학교의 이름이 된다.

 N개 대학교의 이름 s1, s2, ⋯, sN과 회의에서 고른 i, j가 순서대로 주어질 때, 회의를 통해 정해진 통합된 학교의 이름을 구하는 프로그램을 작성해 보자.

 

입력

첫 번째 줄에 대학교의 개수 N이 주어진다. (2 ≤ N ≤ 500,000)

다음 N개의 줄의 i번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 si가 주어진다. 주어지는 대학교 이름의 길이 합은 500,000을 넘지 않는다.

다음 N − 1개의 줄에 회의에서 고른 i, j가 공백을 사이에 두고 차례로 주어진다. (1 ≤ i, j ≤ N; i ≠ j)

주어지는 순서대로 회의를 진행할 때 si, sj가 빈 문자열이 아닌 i, j만 입력으로 주어진다.

 

출력

첫 번째 줄에 회의를 통해 정해진 통합된 학교의 이름을 출력한다.

 

예제 입력 1

5
sogang
sookmyung
yonsei
ewha
hongik
2 3
1 2
4 5
1 4

예제 출력 1

sogangsookmyungyonseiewhahongik

 

알고리즘 분류

• 그래프 탐색

 

풀이

Vector 배열을 선언하고, 각 인덱스마다 다음으로 이어 붙일 문자열의 인덱스들을 Vector에 저장한다.

그리고 DFS로 다음으로 이어 붙일 문자열들을 탐색하며 출력한다.

 

코드

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

using namespace std;
int N, I, J;
string S[MAX];
vector<int> Vec[MAX];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> S[i];
	}
	for (int i = 0; i < (N - 1); i++) {
		cin >> I >> J;
		Vec[I].push_back(J);
	}
}

void dfs(int Now) {
	cout << S[Now];
	
	if (Vec[Now].empty()) return;
	for (int i = 0; i < (int)Vec[Now].size(); i++) {
		int Next = Vec[Now][i];
		dfs(Next);
	}
}

void settings() {
	dfs(I);
}

int main() {
    FASTIO

	input();
	settings();

    return 0;
}