[C++] 그래프 최단거리(BFS) ⭐

📄문제

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

 

⬇️ 입력

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5

 

⬆️ 출력

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

2 : 3 3 : 1 4 : 1 5 : 2 6 : 2

 

📝 풀이

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

vector<int> map[20]; // 인접 리스트
bool visited[20];

int main()
{
	int N, M;
	scanf_s("%d %d", &N, &M);

	int f, t; // from, to
	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d", &f, &t);
		map[f - 1].push_back(t - 1);
	}

	queue<int> visit;
	visit.push(0); // 0번 노드부터 시작
	visited[0] = true;
	int distance[20];

	distance[0] = 0;

	while (!visit.empty())
	{
		// 현재 위치를 가져오기
		int currentNode = visit.front();
		visit.pop();

		for (int i = 0; i < map[currentNode].size(); ++i)
		{
			// 해당 노드를 방문하지 않았다면?
			if (!visited[map[currentNode][i]])
			{
				// 해당 노드를 방문
				visited[map[currentNode][i]] = true;

				// 방문 거리는 현재 노드의 누적 거리 + 1
				distance[map[currentNode][i]] = distance[currentNode] + 1;

				// 큐에 삽입
				visit.push(map[currentNode][i]);
			}
		}
	}

	for (int i = 0; i < N; ++i)
		printf("%d : %d\n", i + 1, distance[i]);
}

• 큐를 이용하여 노드를 방문합니다.
• visited는 해당 노드에 방문하였는지 검사하기 위해 사용됩니다. 다음 노드에 방문하기위해 검사할 때, true가 되어있으면, 이미 최단거리로 다른 노드에서 방문을 했기때문에 더 이상 방문하지 않아도 됩니다.
• 방문하지 않은 노드라면, 현재 노드의 누적된 거리 + 1을 하여 다음 노드의 거리를 설정해줍니다.