# 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)