Memo
로직 설명
공통 - 현재 index를 기준으로 인접해 있는 노드들을 탐색합니다.
•
깊이 우선 탐색(DFS) - 인접한 노드들을 바로 다 방문하지 않고, 현재 인접한 노드들 중 첫 번째 노드를 방문하고, 그 방문한 노드와 인접한 노드들 중 첫 번째 노드를 방문하는 식으로 탐색합니다.
•
너비 우선 탐색(BFS) - 인접한 노드들을 모두 탐색하고, 그 인접한 노드들의 인접한 노드들을 탐색합니다.
자료 구조
•
DFS, BFS
코드 설명
•
void dfs(int index)
std::sort(graph[index].begin(), graph[index].end());
→ 현재 인접한 노드들은 오름차순이어야 하기 때문에 정렬해줍니다.
어려웠던 부분 
PASS
개선할 부분
PASS
Code
제출 날짜
@4/9/2021
메모리
2308 KB
시간
0 ms
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
int N, M, V;
std::vector<int> graph[1001];
bool visited[1001];
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int a, b;
input_faster();
std::cin >> N >> M >> V;
for (int i = 0 ; i < M ; i++)
{
std::cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
void dfs(int index)
{
std::cout << index << " ";
std::sort(graph[index].begin(), graph[index].end());
for (size_t i = 0 ; i < graph[index].size(); i++)
{
if (visited[graph[index][i]])
continue;
visited[graph[index][i]] = 1;
dfs(graph[index][i]);
}
}
void bfs()
{
int x;
std::queue<int> q;
q.push(V);
visited[V] = 1;
while(!q.empty())
{
x = q.front();
q.pop();
std::cout << x << " ";
for (size_t i = 0 ; i < graph[x].size() ; i++)
{
if (visited[graph[x][i]])
continue;
visited[graph[x][i]] = 1;
q.push(graph[x][i]);
}
}
}
void solve()
{
visited[V] = 1;
dfs(V);
std::cout << "\n";
std::memset(visited, 0, sizeof(visited));
bfs();
}
int main()
{
input();
solve();
return (0);
}
C++
복사
