# DFS & BFS



κ·Έλž˜ν”„ μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, 문제λ₯Ό ν’€ λ•Œ μƒλ‹Ήνžˆ 많이 μ‚¬μš©ν•œλ‹€.

경둜λ₯Ό μ°ΎλŠ” 문제 μ‹œ, 상황에 맞게 DFS와 BFSλ₯Ό ν™œμš©ν•˜κ²Œ λœλ‹€.


# DFS

루트 λ…Έλ“œ ν˜Ήμ€ μž„μ˜ λ…Έλ“œμ—μ„œ λ‹€μŒ 브랜치둜 λ„˜μ–΄κ°€κΈ° 전에, ν•΄λ‹Ή 브랜치λ₯Ό λͺ¨λ‘ νƒμƒ‰ν•˜λŠ” 방법

μŠ€νƒ or μž¬κ·€ν•¨μˆ˜λ₯Ό 톡해 κ΅¬ν˜„ν•œλ‹€.


  • λͺ¨λ“  경둜λ₯Ό λ°©λ¬Έν•΄μ•Ό ν•  경우 μ‚¬μš©μ— 적합

# μ‹œκ°„ λ³΅μž‘λ„

  • 인접 ν–‰λ ¬ : O(V^2)
  • 인접 리슀트 : O(V+E)

VλŠ” 접점, EλŠ” 간선을 λœ»ν•œλ‹€


# μ†ŒμŠ€ μ½”λ“œ

#include <stdio.h>

int map[1001][1001], dfs[1001];

void init(int *, int size);

void DFS(int v, int N) {

	dfs[v] = 1;
	printf("%d ", v);

	for (int i = 1; i <= N; i++) {
		if (map[v][i] == 1 && dfs[i] == 0) {
			DFS(i, N);
		}
	}

}

int main(void) {

	init(map, sizeof(map) / 4);
	init(dfs, sizeof(dfs) / 4);

	int N, M, V;
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		int start, end;
		scanf("%d%d", &start, &end);
		map[start][end] = 1;
		map[end][start] = 1;
	}

	DFS(V, N);

	return 0;
}

void init(int *arr, int size) {
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}


# BFS

루트 λ…Έλ“œ λ˜λŠ” μž„μ˜ λ…Έλ“œμ—μ„œ μΈμ ‘ν•œ λ…Έλ“œλΆ€ν„° λ¨Όμ € νƒμƒ‰ν•˜λŠ” 방법

큐λ₯Ό 톡해 κ΅¬ν˜„ν•œλ‹€. (ν•΄λ‹Ή λ…Έλ“œμ˜ μ£Όλ³€λΆ€ν„° νƒμƒ‰ν•΄μ•Όν•˜κΈ° λ•Œλ¬Έ)


  • μ΅œμ†Œ λΉ„μš©(즉, λͺ¨λ“  곳을 νƒμƒ‰ν•˜λŠ” 것보닀 μ΅œμ†Œ λΉ„μš©μ΄ μš°μ„ μΌ λ•Œ)에 적합

# μ‹œκ°„ λ³΅μž‘λ„

  • 인접 ν–‰λ ¬ : O(V^2)
  • 인접 리슀트 : O(V+E)

# μ†ŒμŠ€ μ½”λ“œ

#include <stdio.h>

int map[1001][1001], bfs[1001];
int queue[1001];

void init(int *, int size);

void BFS(int v, int N) {
	int front = 0, rear = 0;
	int pop;

	printf("%d ", v);
	queue[rear++] = v;
	bfs[v] = 1;

	while (front < rear) {
		pop = queue[front++];

		for (int i = 1; i <= N; i++) {
			if (map[pop][i] == 1 && bfs[i] == 0) {
				printf("%d ", i);
				queue[rear++] = i;
				bfs[i] = 1;
			}
		}
	}

	return;
}

int main(void) {

	init(map, sizeof(map) / 4);
	init(bfs, sizeof(bfs) / 4);
	init(queue, sizeof(queue) / 4);

	int N, M, V;
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++)
	{
		int start, end;
		scanf("%d%d", &start, &end);
		map[start][end] = 1;
		map[end][start] = 1;
	}

	BFS(V, N);

	return 0;
}

void init(int *arr, int size) {
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

μ—°μŠ΅λ¬Έμ œ : [BOJ] DFS와 BFS (opens new window)


# [참고 자료]

μ΅œμ’… μˆ˜μ • : 11/15/2021, 1:31:19 PM