[G5] 백준 34949번 이대로 가면 되나요? C++ BFS, 너비 우선 탐색

리뷰

 

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

N번 노드에서 모든 노드까지의 거리를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• dist : n번 노드에서 모든 노드까지의 거리를 저장할 배열
• edges : 간선 정보를 저장할 정수형 벡터 배열

 

함수

1. bfs

void bfs()
{
	queue< int > q;
	q.push( n );
	dist[ n ] = 0;

	while ( !q.empty() )
	{
		int cn = q.front(); q.pop();

		for ( int nn : edges[ cn ] )
		{
			if ( dist[ nn ] != -1 )
				continue;

			dist[ nn ] = dist[ cn ] + 1;
			q.push( nn );
		}
	}
}

 

너비 우선 탐색을 통해 n번 노드로부터 모든 노드로까지의 거리를 구해 dist를 초기화 하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, memset함수를 통해 dist배열의 값을 -1로 초기화한다.
2. n개 노드의 간선을 입력 받아 edges를 초기화한다.
3. bfs함수를 통해 dist배열에 n번 노드에서 모든 노드로의 거리를 저장한다.
4. 1번 노드부터 n번 노드까지 순회하며 dist에 저장된 값을 출력하고, 개행문자를 삽입하여 줄바꿈을 수행한다.

 

 

트러블 슈팅

없음

 

 

참고 사항

1. 입력과 출력의 양이 많으므로 빠른 입출력을 권장한다.
2. i번장소에서 Ai번장소로 이동하므로 단방향 간선을 추가해주었다.
3. memset을 통해 초기값을 -1로 저장하여 방문 불가 지역에 대해 자동으로 -1을 적용해주었다.

 

정답 코드

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

const int N = 2e5 + 1;
int n;
int dist[ N ];
vector< int > edges[ N ];

void bfs()
{
	queue< int > q;
	q.push( n );
	dist[ n ] = 0;

	while ( !q.empty() )
	{
		int cn = q.front(); q.pop();

		for ( int nn : edges[ cn ] )
		{
			if ( dist[ nn ] != -1 )
				continue;

			dist[ nn ] = dist[ cn ] + 1;
			q.push( nn );
		}
	}
}

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

	cin >> n;
	memset( dist, -1, sizeof( dist ) );
	for ( int i = 1; i <= n; ++i )
	{
		int t; cin >> t;
		edges[ t ].push_back( i );
	}

	bfs();

	for ( int i = 1; i <= n; ++i )
		cout << dist[ i ] << '\n';
}