Tree BFS 탐색 순서
BFS는 레벨 단위로 탐색을 한다.
즉 한 번 만에 갈 수 있는 길을 모두 탐색한후, 두 번 만에 갈수 있는 모든 길을 탐색하는 방식이다.
BFS의 특징
•
두 노드사이의 최단경로를 탐색할때 활용하기 좋은 방식이다. 멀리떨어진 노드는 나중에 탐색하는 방식이기 때문!
•
큐를 활용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색한다. 선입선출의 방식을 활용해야 하기 때문에 큐를 활용한다.
BFS 구현 알고리즘
1.
루트노드에서 시작한다.
2.
루트노드와 인접하고 방문된적 없고, 큐에 저장되지 않은 노드를 Queue에 넣는다.
3.
Queue에서 dequeue(pop)하여 가장 먼저 큐에 저장한 노드를 방문한다.
배열을 큐처럼 활용한 트리 BFS 순회 방법
#include <iostream>
int map[6][6] =
{
{0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
char value[6] = { 'E', 'A', 'U', 'R', 'Q', 'Y' };
struct Node
{
int num;
int level;
};
Node queue[7] = { {0,0} };
int head = 0;
int tail = 1;
int main()
{
while (head != tail)
{
Node now = queue[head];
std::cout << value[now.num] << std::endl;
std::cout << "------------" << std::endl;
for (int i = 0; i < 6; i++)
{
if (map[now.num][i] == 1)
{
queue[tail] = { i, now.level + 1 };
tail++;
}
}
head++;
}
return 0;
}
JavaScript
복사
bfs 트리 순회 std::Queue 라이브러리를 사용한 방법
#include <iostream>
#include <queue>
int map[6][6] =
{
{0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
char value[6] = { 'E', 'A', 'U', 'R', 'Q', 'Y' };
struct Node
{
int num;
int level;
};
std::queue<Node> queue = {};
int main()
{
queue.push(Node{0, 0});
while (!queue.empty())
{
Node now = queue.front();
std::cout << value[now.num] << std::endl;
std::cout << "------------" << std::endl;
for (int i = 0; i < 6; i++)
{
if (map[now.num][i] == 1)
{
queue.push(Node{ i, now.level + 1 });
}
}
queue.pop();
}
return 0;
}
JavaScript
복사
그래프 BFS 탐색순서
그래프토 트리순회와 크게 다른 점은 없다. 다만 이미 방문한 노드를 2번 방문하지 않기 위한 예외처리만 진행해주면 된다.
bfs 그래프 순회 방법
#include <iostream>
#include <queue>
int map[5][5] =
{
{0, 1, 0, 1, 1,},
{0, 0, 1, 1, 0,},
{0, 0, 0, 0, 0,},
{0, 0, 0, 0, 1,},
{0, 0, 0, 0, 0,},
};
char value[6] = { 'E', 'B', 'R', 'A', 'Y'};
struct Node
{
int num;
int level;
};
std::queue<Node> queue = {};
int used[6] = {};
int main()
{
queue.push(Node{0, 0});
used[0] = 1;
while (!queue.empty())
{
Node now = queue.front();
std::cout << value[now.num] << std::endl;
std::cout << "------------" << std::endl;
for (int i = 0; i < 5; i++)
{
if (used[i] == 1)
continue;
if (map[now.num][i] == 0)
continue;
used[i] = 1;
queue.push(Node{ i, now.level + 1 });
}
queue.pop();
}
return 0;
}
JavaScript
복사
BFS 길찾기 맵 탐색
bfs 알고리즘은 단순 순회 외에도 길찾기 알고리즘으로 활용 하는 경우도 많다.
다만 여기에서는 당장 길찾기에 활용 하면 복잡할 수 있기에 2차원 배열을 bfs를 이용해 순회하는 방법부터 연습해보도록 하겠다. (다음 시간에 길찾기 bfs활용)
BFS 2차원 배열 길찾기 사전준비 ( 2차원배열 BFS로 순회하기 )
#include <iostream>
#include <queue>
int map[3][3] =
{
{0, 0, 0},
{0, 0, 0},
{0, 0, 0},
};
struct Node
{
int x;
int y;
int level;
};
std::queue<Node> queue = {};
int used[6] = {};
int direct[4][2] =
{
0, 1,
0, -1,
1, 0,
-1, 0,
};
int main()
{
queue.push(Node{1, 0, 1});
map[0][1] = 1;
while (!queue.empty())
{
Node now = queue.front();
if (now.y == 2 && now.x == 2)
{
int t = 0;
}
for (size_t i = 0; i < 4; i++)
{
int dy = now.y + direct[i][0];
int dx = now.x + direct[i][1];
if (dy < 0 || dx < 0 || dy > 2 || dx > 2)
continue;
if (map[dy][dx] > 0)
continue;
Node next = Node{ dx, dy, now.level + 1 };
map[dy][dx] = next.level;
queue.push(next);
int a = 0;
}
queue.pop();
}
return 0;
}
JavaScript
복사
“강의는 많은데, 내 실력은 왜 그대로일까?”
혼자서 공부하다 보면
이런 생각 들지 않으셨나요?
•
강의는 다 듣고도 직접 코드는 못 짜겠고,
•
복습할 땐 어디서부터 다시 시작해야 할지 막막하고,
•
질문하려 해도 물어볼 사람이 없고,
•
유튜브 영상도 정답만 보고 따라 치는 느낌…
그렇다면 지금이 바로
“나만을 위한 코칭”이 필요한 순간입니다.
당신도 할 수 있습니다.
지금 멤버십을 넘어, 코칭에 도전해보세요.
수많은 수강생들이 얌얌코딩 코칭으로 넥슨, 크래프톤, NC 등 입사에 성공했습니다.
또는 카톡 오픈채팅: 얌얌코딩 상담방지금도 코딩을 ‘따라 치기만’ 하고 계신가요?
이젠 혼자 설계하고, 스스로 코딩하는 법을 배워야 할 때입니다.
얌얌코딩이 옆에서 함께하겠습니다.
