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

백준 온라인 저지(BOJ) 24444번 알고리즘 수업 - 너비 우선 탐색 1
https://www.acmicpc.net/problem/24444

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

* 사용언어 : C언어, C++
 

1. 문제

graph 를 BFS(너비 우선 탐색)으로 탐색할 때
1번 정점부터 N번 정점까지 방문한 순서를 출력
(인접 정점은 오름차순으로 방문)
 

2. 풀이

BFS 함수 구현은 문제에 적혀있는 의사 코드만으로 충분히 설명이 되는 것 같습니다.
 
BFS 설명 대신 인접 정점 정보를 저장하는 인접 리스트에 대한 내용과
방문 처리를 위한 queue 구현에 대한 내용을 소개하겠습니다.
 
인접 리스트는 앞서 DFS(깊이 우선 탐색)을 풀면서 사용했던 방식을 그대로 적용했습니다.
(① vector, ② algorithm 의 sort 메소드 활용)
 
인접 리스트 관련 내용은 아래 링크 참고 바랍니다.
https://rightbellboy.tistory.com/242

[백준/BOJ] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (C/C++)

 
queue 는 제가 선호하는 투 포인트 방식으로 구현했습니다.
 
이 방식으로 구현하면 따로 구조체를 만들지 않고 배열과 2개의 포인터만 있으면 됩니다.
(정확히 말하자면, 포인터 변수를 두는 것은 아니고 int 변수로 index 를 기억)
 
queue 의 맨 앞(front)과 맨 뒤(rear)를 index 로 저장해두고 사용하는 방식입니다.

• enqueue : queue 의 re 자리에 값을 넣고, re 1 증가
• dequeue : queue 의 fr 자리에서 값을 빼고, fr 1 증가
• isEmpty() : fr 이 re 과 같으면 empty (queue 에 값이 있으면 fr < re)

 
이 방식은 library 를 사용하지도 않을 뿐만 아니라 상당히 빠르기 때문에
구동 시간이 중요한 알고리즘 시험에 적합하다고 볼 수 있습니다.
 
문제 조건에 따라 메모리 제한에 걸려서 못 쓰는 경우도 종종 있는데
통상 BFS 문제는 visited 를 보고 queue 에 넣기 때문에 충분히 구현 가능한 사이즈가 됩니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24444_알고리즘 수업 - 너비 우선 탐색 1
8512KB	108ms
*/
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int LM = 100001;
vector<int> graph[LM];
int visited[LM], seq = 1;
int que[LM], fr, re;


void bfs(int r) {
	visited[r] = seq++;
	que[re++] = r; // enqueue

	int u;
	while (fr < re) {
		u = que[fr++]; // dequeue
		for (int i = 0; i < graph[u].size(); ++i) {
			if (!visited[graph[u][i]]) {
				visited[graph[u][i]] = seq++;
				que[re++] = graph[u][i]; // enqueue
			}
		}
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, s, u, v;
	scanf("%d %d %d", &n, &m, &s);

	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		if (u != s) graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) sort(graph[i].begin(), graph[i].end());
	bfs(s);

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