DFS & BFS ๊ตฌํ
๋ค์ด๊ฐ๋ฉฐ
2020-1ํ๊ธฐ, ๋ํ์์ โ์๊ณ ๋ฆฌ์ฆโ ์์ ์ ๋ฃ๊ณ ๊ณต๋ถํ ๋ฐ๋ฅผ ์ ๋ฆฌํ ๊ธ์ ๋๋ค. ์ง์ ์ ์ธ์ ๋ ํ์์ ๋๋ค :) ์ ์ฒด ํฌ์คํธ๋ Algorithm ํฌ์คํธ์์ ํ์ธํ์ค ์ ์์ต๋๋ค.
<DFS>, <BFS>์ ๋ํ ๊ธฐ์ด ๋ฐฑ์ค ๋ฌธ์ ์ธ 1260๋ฒ - DFS์ BFS ๊ธฐ์ค์ผ๋ก ์ฝ๋๋ฅผ ์์ฑํด๋ณด์๋ค.
Set-up
์ ๋ ๊ทธ๋ํ์ edge $E$๋ฅผ ์ ์ฅํ ๋, โ์ธ์ ๋ฆฌ์คํธ(Adjacency List)โ ๋ฐฉ์์ ์ ํธ ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ bool
ํ์
์ ๋ฐฐ์ด isVisit[]
๋ก ๊ธฐ๋ก ํฉ๋๋ค.
vector<int> edges[MAX];
bool isVisit[MAX];
๊ทธ๋ฆฌ๊ณ ๋ฐ์ดํฐ๋ฅผ ๋ฃ๋๊ฑด ์๋ ๊ฒ
for (int i = 0; i < M; i++) {
int s, e;
scanf("%d %d", &s, &e);
edges[s].push_back(e);
edges[e].push_back(s);
}
DFS
Recursion
void dfs(int v) {
printf("%d ", v);
isVisit[v] = true;
for (int i = 0; i < edges[v].size(); i++) {
int adj = edges[v][i];
if (!isVisit[adj]) {
dfs(adj);
}
}
}
Stack
void dfs_stack(int s) {
stack<int> st;
st.push(s);
while (!st.empty()) {
int top = st.top();
st.pop();
if(!isVisit[top]){
isVisit[top] = true;
printf("%d ", top);
for (int i = 0; i < edges[top].size(); i++) {
int adj = edges[top][i];
if (!isVisit[adj]) {
st.push(adj);
}
}
}
}
}
BFS
void bfs(int s) {
queue<int> q;
isVisit[s] = true;
q.push(s);
while (!q.empty()) {
int front = q.front();
printf("%d ", front, q.size());
q.pop();
for (int i = 0; i < edges[front].size(); i++) {
int adj = edges[front][i];
if (!isVisit[adj]) {
q.push(adj);
isVisit[adj] = true;
}
}
}
}
DFS-BFS ํธํ ์ฝ๋
๋ช๋
๊ฐ์ PS ๊ฒฝํ์ ๋ฐ๋ฅด๋ฉด, <DFS>์ ๊ตฌํ ์ฝ๋์ <BFS>์ ๊ตฌํ ์ฝ๋์ ํํ๋ฅผ ๊ฑฐ์ ์ผ์น์ํฌ ์ ์๋ ๊ตฌํ ์คํ์ผ์ด ์์ต๋๋ค. ์ด ์คํ์ผ์ stack
์ ์ฐ๋ฉด DFS๊ฐ ๋๊ณ , queue
๋ฅผ ์ฐ๋ฉด BFS๊ฐ ๋ฉ๋๋ค!
1. DFS (stack)
void dfs_stack(int s) {
stack<int> st; // stack ์ฌ์ฉ
st.push(s);
while (!st.empty()) {
int top = st.top();
st.pop();
if(!isVisit[top]){
isVisit[top] = true;
printf("%d ", top);
for (int i = 0; i < edges[top].size(); i++) {
int adj = edges[top][i];
if (!isVisit[adj]) {
st.push(adj);
}
}
}
}
}
2. BFS (queue)
void bfs_queue(int s) {
queue<int> q; // queue๋ฅผ ์ฌ์!
q.push(s);
while (!q.empty()) {
int front = q.front();
q.pop();
if(!isVisit[front]){
isVisit[front] = true;
printf("%d ", front, q.size());
for (int i = 0; i < edges[front].size(); i++) {
int adj = edges[front][i];
if (!isVisit[adj]) {
q.push(adj);
}
}
}
}
}
์ฝ๋๋ฅผ ์ ์ดํด๋ณด๋ฉด, Container๋ก stack
์ ์ ํํ๋์ง, queue
๋ฅผ ์ ํํ๋์ง์ ๋ฐ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด ๋ฐ๋๊ฑด ๋ณผ ์ ์์ต๋๋ค.
๊ฐ์ธ์ ์ผ๋ก ์์ฃผ ์ฐ๋ ์คํ์ผ์ ์๋๋ฐ, <DFS>, <BFS> ์ฝ๋๋ฅผ ์ฌ๋ฌ ๋ฒ ๊ตฌํํด๋ณด๋ ์ด๋ฐ ํจํด๋ ๋ณด์ด๊ฒ ๋์์ต๋๋ค ใ ใ ๐ ํ์ง๋ง ์ฌ์ ํ <DFS> ๊ตฌํ์ <์ฌ๊ท recursion>์ผ๋ก ๊ตฌํํ๋ ๊ฑธ ์ ํธํ๋ ๊ฒ ๊ฐ์ต๋๋ค ๐