Unity ToyProject/Defence
BFS 알고리즘
김조성준
2023. 8. 7. 15:10
1. BFS
BFS는 시작 노드를 큐에 넣고 시작합니다. 그 후는 큐에서 나온 노드의 인접 노드를 큐에 삽입하고, 더 이상 삽입할 노드가 없다면 큐에서 다시 노드를 빼오는 것을 반복합니다. 더이상 큐에서 빼올 노드가 없다면 종료합니다.
기본적인 코드는 다음과 같습니다. (백준 1260번을 풀 때 사용한 코드입니다)
vector<int> vec[10002];
bool visit[1002];
void bfs(int temp) {
queue<int> q;
q.push(temp);
visit[temp] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
result_bfs.push_back(x);
for (int i = 0; i < vec[x].size(); i++) {
if (!visit[vec[x][i]]) {
q.push(vec[x][i]);
visit[vec[x][i]] = true;
}
}
}
}
적이 경로를 찾는 방법에 대해서 적어봤습니다.

● BFS로 경로를 찾았지만, 다익스트라, A* 알고리즘 .. 등 상황에 따라 다른 알고리즘이 더 좋은 방법이 될 수 있습니다.