🙇‍♀️그래프 최단거리(BFS)

다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.

graph

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.

그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

▣ 출력설명
1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

▣ 입력예제 1 
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5

▣ 출력예제 1
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2

🚀풀이

위의 문제를 풀기 위한 그래프 최단 거리 알고리즘 기록.

일반적인 BFS와 똑같이 적되, 거리를 기록하는 배열이 필요하다.

vector<int> dist(21);
이런식으로 잡고 BFS에서는 다음 정점을 발견할 때, 거리를 그위치까지의 거리에서 1을 더해준 값으로 저장한다.

dist[board[here][there]] = dist[here] + 1;
이런식으로 해준다.

아래는 BFS를 구현한 코드이다.

void BFS(int here)
{
	queue<int> q;
	q.push(here);

	while (q.empty() == false)
	{
		int here = q.front();
		q.pop();

		for (int there = 0; there < board[here].size(); ++there)
		{
			if (discovered[board[here][there]])
				continue;

			discovered[board[here][there]] = true;
			q.push(board[here][there]);
			dist[board[here][there]] = dist[here] + 1;
		}
	}
}

위의 방식은 그래프가 인접리스트로 그려질 경우를 상정하고 코드를 작성한 것이다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> board[21];
vector<bool> discovered(21);
vector<int> dist(21);
int n, m;

void setting()
{
	cin >> n >> m;

	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		cin >> a >> b;
		board[a].push_back(b);
	}
}

void BFS(int here)
{
	queue<int> q;
	q.push(here);

	while (q.empty() == false)
	{
		int here = q.front();
		q.pop();

		for (int there = 0; there < board[here].size(); ++there)
		{
			if (discovered[board[here][there]])
				continue;

			discovered[board[here][there]] = true;
			q.push(board[here][there]);
			dist[board[here][there]] = dist[here] + 1;
		}
	}
}

void solve()
{
	setting();

	BFS(1);

	for (int i = 2; i <= n; ++i)
		cout << i << " : " << dist[i] << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고