[백준/C++] 31423 신촌 통폐합 계획

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

31423번: 신촌 통폐합 계획

(이 문제는 SUAPC 2024 Winter에 출제된 문제다. 참고로 나는 대회에 나가서 해당 문제를 풀었다. 오픈 콘테스트가 종료되고 문제가 공개되었길래 코드를 한 번 제출해본 뒤 미리 작성해둔 글을 올린다. 느낀점은 대회 당시 내가 했던 생각들을 옮겼다.)

코드

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

vector<string> v;
vector<vector<int>> arr;

void print(int start)
{
	cout << v[start]; 
	if (arr[start].size() == 0) return;
	for (int i = 0; i < arr[start].size(); i++)
            print(arr[start][i]);
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, a, b;
	cin >> n;
	v.resize(n + 1);
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) cin >> v[i];

	for (int i = 0; i < n - 1; i++)
	{
		cin >> a >> b;
		arr[a].push_back(b);
	}
	print(a);
	return 0;
}

설명

반복문을 이용해서 문자열을 입력받고 벡터에 저장해나간다. 이후  n-1번의 반복문을 통해 a, b를 입력받는다. 이는 a 인덱스에 해당하는 문자열 뒤에 b 인덱스에 해당하는 문자열을 붙인다는 의미이므로 인덱스 b를 문자열 a의 인덱스에 대한 벡터에 저장해나간다. (트리를 인접 리스트로 구현한다.)
 
이후 재귀함수인 print()를 호출한다. (트리를  dfs로 탐색하며 출력한다.) 마지막에 입력된 a를 시작으로 해서 계속 재귀호출을 해서 문자열을 출력해주면 된다.

(대회 당시) 느낀 점

처음에 문제를 읽고 아무 생각 없이 문자열을 더해가며 풀었다가 메모리 초과를 만났다. 그래서 '문자열을 진짜 더해나가면 안 되고 문자열이 더해지는 순서를 기억하고 최종적으로 해당 순서대로 처음에 입력받은 문자열을 연달아 출력하면 되겠다'고 바로 생각했다.연결리스트나 트리를 이용해서 순서를 저장하고 출력해주면 된다는 판단까지 했다.
 
이때 다른 문제들을 많이 못 본 상태라서 다른 문제들을 보고 오는 김에 아이디어를 정리하고 왔다. 처음에는 구조체로 노드를 생성하고 그 노드의 값들을 이용해서 이동하면서 문자열을 출력하게 코드를 짰는데 출력 초과가 났다. 출력초과는 처음 코딩 공부할 때 딱 한 번만 받아봤던 결과라 좀 당황했다. 조금 수정해서 제출했는데도 출력 초과가 나서 바로 방식을 바꿨다.
 
문자열을 합칠 때마다 단순하게 그냥 벡터를 이용해서 연결될 인덱스를 저장해줬다. 이후 특정 벡터의 원소가 없을 때 return하도록 재귀 함수를 짰고 이 재귀함수의 시작을 마지막에 입력된 a로 했다. 너무 쉽게 짠 코드라서 크게 기대하지 않았는데 바로 통과해서 당황스러웠다.