BaekJoon 9372번: 상근이의 여행(C++)

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

9372번: 상근이의 여행

풀이법

1) 그래프 이론을 활용하여, BFS나 DFS로 푸는 문제라 생각하여 시도 하였으나, 어이 없게도 답은 무조건 n-1이 나오는 문제이다.

2) 그래프 내의 모든 정점을 포함하는 트리이며, 최소 연결 부분 그래프이기에, MST로 문제를 푸는 것이 맞는데, n개의 정점을 갖는 MST의 최소 간선의 수는 n-1개 이기에 답은 항상 n-1이 된다.

3) 해당 첨부한 소스코드는 클린 코드가 아니기에 조금 부끄럽지만, 접근을 이렇게 한 사람도 있구나 정도로 봐주었으면 좋겠다. 물론, queue에 값을 넣을떄 마다 cnt를 증가시켰기에 정답을 얻을 수 있었다.

#include <string>
#include <iostream>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int t;
int n, m;
int visited[1001];
int arr[1001][1001];
int cnt = 0;
void clearArr(int a)
{
	for (int i = 1; i <= a; i++)
	{
		visited[i] = INF;
		for (int j = 1; j <= a; j++)
		{
			arr[i][j] = 0;
		}
	}
}
void bfs(int a)
{
	queue<pair<int,int>> q;
	q.push({ a,0 });
	visited[a] = 0;
	int cnt = 0;
	while (!q.empty())
	{
		int now = q.front().first;
		int count = q.front().second;
		q.pop();
		bool check = false;
		for (int i = 1; i <= n; i++)
		{
			if (arr[now][i] == 1)
			{
				if (visited[i] > count + 1)
				{
					check = true;
					visited[i] = count+1;
					q.push({ i,count + 1 });
					cnt++;
				}
			}
		}
	}
	cout << cnt<<"\n";
}
void visitedCheck()
{
	for (int i = 1; i <= n; i++)
		cout << visited[i] << " ";
	cout << endl;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> t;
	while (t > 0)
	{
		cin >> n >> m;
		clearArr(n);
		for (int i = 0; i < m; i++)
		{
			int a, b;
			cin >> a >> b;
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		cnt = 0;
		bfs(1);

		t--;
	}
}