BOJ #1260 : DFS와 BFS
2019년 01월 14일
DFS
int dfs(int pos)
{
printf("%d ", pos);
visited[pos] = 1;
for (int i = 1; i <= n; i++)
{
if (visited[i] == 0 && edge[pos][i] > 0) dfs(i);
}
}
트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.
BFS
int bfs(int pos)
{
int x;
queue<int> q;
q.push(pos);
visited[pos] = 1;
while(!q.empty())
{
x = q.front();
printf("%d ", x);
q.pop();
for (int i = 1; i <= n; i++)
{
if (edge[x][i] > 0 && visited[i] == 0){
visited[i] = 1;
q.push(i);
}
}
}
}
1260번 : 문제풀이
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int edge[1001][1001];
int visited[1001];
int n, m, v;
int dfs(int pos);
int bfs(int pos);
int main()
{
int a, b;
memset(edge, 0,sizeof(edge));
memset(visited, 0, sizeof(visited));
scanf("%d %d %d", &n, &m, &v);
for (int i = 0; i < m; i++)
{
scanf("%d %d\n", &a, &b);
edge[a][b] += 1;
edge[b][a] += 1;
}
dfs(v);
memset(visited, 0, sizeof(visited));
printf("\n");
bfs(v);
}
int dfs(int pos)
{
printf("%d ", pos);
visited[pos] = 1;
for (int i = 1; i <= n; i++)
{
if (visited[i] == 0 && edge[pos][i] > 0) dfs(i);
}
}
int bfs(int pos)
{
int x;
queue<int> q;
q.push(pos);
visited[pos] = 1;
while(!q.empty())
{
x = q.front();
printf("%d ", x);
q.pop();
for (int i = 1; i <= n; i++)
{
if (edge[x][i] > 0 && visited[i] == 0){
visited[i] = 1;
q.push(i);
}
}
}
}
벡터를 도입한 코드
정답을 맞추기 위해서는 각 벡터들을 sort해줘야 합니다. 아니면 auto 키워드를 사용하지 않으면 됩니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int visited[1001];
int n, m, v;
vector<int> edge[1001];
int dfs(int pos);
int bfs(int pos);
int main()
{
int a, b;
memset(visited, 0, sizeof(visited));
scanf("%d %d %d", &n, &m, &v);
for (int i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
edge[a].push_back(b);
edge[b].push_back(a);
}
for (int i = 0; i < n; i++)
{
if(edge[i].size())
{
sort(edge[i].begin(), edge[i].end());
}
}
dfs(v);
memset(visited, 0, sizeof(visited));
printf("\n");
bfs(v);
}
int dfs(int pos)
{
visited[pos] = 1;
printf("%d ", pos);
for (auto next : edge[pos])
{
if (visited[next] == 0) dfs(next);
}
}
int bfs(int pos)
{
queue<int> q;
q.push(pos);
visited[pos] = 1;
while(!q.empty())
{
int now = q.front();
q.pop();
printf("%d ", now);
for (auto next : edge[now])
{
if (visited[next] == 0)
{
visited[next] = 1;
q.push(next);
}
}
}
}