[ 그래프 이론 - 9372번 ] 상근이의 여행(C++)

Intro

앞으로 모든 백준 문제는 C++로 해결하고자 한다. 코테를 위해서는 Python이 더 편하지만, 실제 실력을 더 향상시킬 수 있는 것은 C++이기 때문에 코테 준비는 나중에 하기로 했다. 또한, 이번에 자율주행 경진대회를 준비하면서 코드 통합을 진행 하였는데 변수명을 선언하는 것이 전부 다 달라서 애먹었다. 앞으로는 박사님이 정해주신 틀 안에서 타인이 봐도 알아볼 수 있도록 변수명을 통합할 것이다.

---

---

접근법

비행기 종류는 vector로 저장하면 된다. a,b쌍은 a,b를 왕복하는 비행기가 있음을 의미하기에 vector 배열의 a와 b index에 모두 저장해야 한다. 

모든 국가를 여행하기 위해서 각 국가를 방문했음을 확인하기 위한 bool 형 array가 요구된다. 

또한 저장한 비행기 종류를 기반으로 각 국가를 방문하는 과정을 queue 자료형을 통해 구현 가능하다. vector에는 각 index에 해당하는 국가에서 갈 수 있는 국가들에 대한 정보가 저장되어 있다. 따라서 갈 수 있는 국가에 대해서 만약 방문하지 않았더라면 queue에 집어넣고, while문을 queue가 empty일 때 까지 반복하여 모든 국가를 탐색하면 된다.

---

정답

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int32_t> ars32_Graph[1001];
bool arb_Check[1001];

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

	int32_t s32_Cnt,s32_I;
	cin >> s32_Cnt;

	for (s32_I = 0; s32_I < s32_Cnt; s32_I++)
	{
		int32_t s32_Node, s32_Edge, s32_A, s32_B, s32_J;
		cin >> s32_Node >> s32_Edge;
		// Graph, Check 초기화
		for (s32_J = 1; s32_J <= s32_Node; s32_J++)
		{
			ars32_Graph[s32_J].clear();
			arb_Check[s32_J] = false;
		}

		// Graph 생성
		for (s32_J = 0; s32_J < s32_Edge; s32_J++)
		{
			cin >> s32_A >> s32_B;
			ars32_Graph[s32_A].push_back(s32_B);
			ars32_Graph[s32_B].push_back(s32_A);
		}

		// 탐색을 위한 queue 생성
		int32_t s32_Result = 0;
		queue<int32_t> qs32_Q;
		qs32_Q.push(1);
		arb_Check[1] = true;

		// 탐색
		while (!qs32_Q.empty())
		{
			int32_t s32_Idx = qs32_Q.front();
			qs32_Q.pop();
			for (s32_J = 0; s32_J < ars32_Graph[s32_Idx].size(); s32_J++)
			{
				int32_t s32_NextIdx = ars32_Graph[s32_Idx][s32_J];
				if (!arb_Check[s32_NextIdx])
				{
					arb_Check[s32_NextIdx] = true;
					s32_Result++;
					qs32_Q.push(s32_NextIdx);
				}
			}
		}
		printf("%d\n", s32_Result);
	}
	return 0;
}