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

 

1) 문제설명

 

백준 Online Judge 24444번 알고리즘 수업 - 너비 우선 탐색 1

백준 Online Judge 24444번 알고리즘 수업 - 너비 우선 탐색 1

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

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

 

2) 아이디어

문제에서 오름차순으로 방문한다고 하였으므로 노드들을 입력받은 후 오름차순으로 정렬한다.

BFS대로 노드를 순회하며 방문한 곳을 체크하고 그 노드를 몇 번째 방문했는지 알기 위해 카운트를 세고 저장한다.

이후 카운트를 저장한 배열을 순서대로 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

vector<int> graph[100001];
int visited[100001] = { 0, };
int result[100001];
int cnt = 0;

void bfs(int r) {
	queue<int> q;
	q.push(r); // 큐에 노드를 집어넣는다
	visited[r] = 1; // 처음 방문한 곳 표시
	cnt++; // 처음 방문한 곳 카운트 + 1
	result[r] = cnt; // 처음으로 방문 cnt == 1
	while (!q.empty()) {
		int inq = q.front(); // 큐에 첫번째 원소 저장

		q.pop(); // 제거

		for (int i = 0; i < graph[inq].size(); i++) { // 노드에 연결된 크기만큼 반복
			int temp = graph[inq][i]; // 
			if (!visited[temp]) { // 노드에 연결된 노드가 방문하지 않은 곳이면
				cnt++;
				result[temp] = cnt;
				q.push(temp); // 큐에 넣고
				visited[temp] = 1; // 방문처리
			}
		}
	}
}
int main() {
	int n, m, r;
	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); // (1,4) (1,2) (2,3) (2,4) (3,4)
		graph[b].push_back(a); // (4,1) (2,1) (3,2) (4,2) (4,3)	
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	bfs(r);
	for (int i = 1; i <= n; i++) {
		printf("%d\n", result[i]);
	}

}

처음에 간단하게 노드들을 입력받고 BFS로 노드 순회를 하여 방문한 순서대로 출력하였는데 3퍼센트에서 계속 틀렸다.

문제를 다시 보니 방문한 순서대로 출력하는 것이 아닌 정점이 몇 번째로 방문되는지를 1~N번 정점에 대해 각각 순서대로 출력하는 것이었다.