1259. [S/W 문제해결 응용] 7일차 - 금속막대

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN&categoryId=AV18NaZqIt8CFAZN&categoryType=CODE

SW Expert Academy

 

예외적인 상황으로 부터 DFS를 통해 하나씩 끼워가야 한다는 것을 알게됨.

 

 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

vector<pair<int, int> > vec;
vector<pair<int, int> > ans;
int N;

void DFS(int test_case)
{

	if (ans.size() == vec.size())
	{

		cout << "#" << test_case << " ";
		for (int i = 0; i < ans.size(); i++)
		{
			cout << ans[i].first << " " << ans[i].second << " ";
		}
		cout << endl;
		return;
	}


	for (int i = 0; i < vec.size(); i++)
	{
		if (vec[i].first == ans[ans.size() - 1].second)
		{
			ans.push_back(vec[i]);
			DFS(test_case);
			ans.pop_back();
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		int am, su;
		ans.clear();
		vec.clear();

		for (int i = 1; i <= N * 2; i++)
		{
			if (i % 2)
			{
				cin >> su;
				
			}
			else
			{
				cin >> am;
				vec.push_back({ su,am });
			}
		}
		
		for (int i = 0; i < vec.size(); i++)
		{
			ans.push_back(vec[i]);
			DFS(test_case);
			ans.pop_back();
		}
		

		
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}