[G5] 백준 17352번 여러분의 다리가 되어 드리겠습니다! C++ 너비 우선 탐색, 분리 집합

리뷰

 

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

그래프에서 다른 그룹인 두 노드의 번호를 출력하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 정수형 상수 변수
• n : 노드의 개수를 저장할 정수형 변수
• v : 방문 여부를 저장할 논리형 배열
• edges : 간선 정보를 저장할 정수형 벡터 배열

 

함수

1. bfs

void bfs()
{
	queue< int > q;
	q.push( 1 );
	v[ 1 ] = true;

	while ( !q.empty() )
	{
		int cn = q.front(); q.pop();
		for ( int nn : edges[ cn ] )
		{
			if ( v[ nn ] )
				continue;

			v[ nn ] = true;
			q.push( nn );
		}
	}
}

 

같은 그래프 내의 노드 방문을 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n-2개의 간선 정보를 입력 받아 edges를 초기화한다.
2. bfs함수를 호출하여 1번 노드에서 방문 할 수 있는 모든 노드에 방문을 수행한다.
3. 2번 노드부터 n번 노드까지 순회하며 방문하지 않은 노드를 만난 경우 1과 i를 공백을 기준으로 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 우선 1번 노드에서 연결되는 모든 노드에 방문처리를 한다.
2. 2번노드부터 순회하며 아직 방문처리되지 않은 노드가 1번 노드와 연결되지 않은 최초의 노드이다.
3. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력하면 되므로 1과 해당 노드번호를 출력한다.

 

정답 코드

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

const int N = 3e5 + 1;
int n;
bool v[ N ];
vector< int > edges[ N ];

void bfs()
{
	queue< int > q;
	q.push( 1 );
	v[ 1 ] = true;

	while ( !q.empty() )
	{
		int cn = q.front(); q.pop();
		for ( int nn : edges[ cn ] )
		{
			if ( v[ nn ] )
				continue;

			v[ nn ] = true;
			q.push( nn );
		}
	}
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );

	cin >> n;
	for ( int i = 0; i < n - 2; ++i )
	{
		int f, t; cin >> f >> t;
		edges[ f ].push_back( t );
		edges[ t ].push_back( f );
	}

	bfs();
	for ( int i = 2; i <= n; ++i )
	{
		if ( v[ i ] )
			continue;

		cout << 1 << " " << i;
		return 0;
	}
}