[백준 24444번 C/C++] 알고리즘 수업 - 너비 우선 탐색 1

 

 

목차

 

 

---

 

 

 

[백준 24444번 C/C++] 알고리즘 수업 - 너비 우선 탐색 1

 

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

---

 

 

해결 전략

 

vector<int> graph[ ]

• 정점

 

int visited[ ]

• 정점 방문 체크

 

int dis[ i ]

• 정점 i 의 방문 순서.

 

int cnt = 1

• 방문 카운팅
• "시작 정점의 방문 순서는 1이다."라고 문제에서 명시되어 있다. 따라서 int cnt의 시작값을 1로 설정.

 

queue<int> Q

• 방문한 정점을 담은 다음 후에 다시 꺼내는 방식으로 BFS를 구현한다.

---

 

코드

 

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

vector<int> graph[100001];
int visited[100001], dis[100001], cnt=1;
queue<int> Q;

int main() {
	int n, m, r, x;
	scanf("%d %d %d", &n, &m, &r);
	
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	
	Q.push(r);
	visited[r]=1;
	
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		dis[x]=cnt++;
		
		for(int i=0; i<graph[x].size(); i++)
		{
			if(visited[graph[x][i]]==0)
			{
				visited[graph[x][i]]=1;
				Q.push(graph[x][i]);
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		printf("%d\n", dis[i]);
	}
	
	return 0;
}

 

 

---