[백준 1260] dfs와 bfs

수정 20190825

문제 링크

https://www.acmicpc.net/problem/1260

문제 요구 사항

1. dfs 출력 결과

1.1 시작 노드 방문 -> 노드와 이어진 노드 방문 -> 깊이 탐색

2. bfs 출력 결과

2.1 시작 노드를  queue에 넣어 bfs 실시

1.1번 풀이

1. 시작 노드 방문 visit check

2. 시작 노드와 이어진 노드 방문 

3. 2번과 이어진 노드 방문 없을 경우 1로

4. 시작 노드와 이어진 거 끝까지 방문

2번 풀이

1. 시작 노드와 이어진 노드들 부터 방문

2. 이어진 노드에서 다시 이어진 노드들 방문

소스코드

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int n, m, k;
int map[1001][1001];
int visit[1001];
queue<int> q;
//dfs 시작
void dfs(int r)
{
    visit[r] = 1;
    cout << r << " ";
    //전체 검색하여 조건맞으면 dfs 시작
    for (int i = 1; i <= n; i++)
    {
        if (map[r][i] == 1 && visit[i] == 0)
        {
            dfs(i);
        }
    }
}
//dfs
void bfs(int r)
{
    visit[r] = 1;
    q.push(r);
    while (!q.empty())
    {
        int x = q.front();
        cout << x << " ";
        q.pop();
        //전체 검색하여 조건에 맞으면 큐에 삽입
        for (int i = 1; i <= n; i++)
        {
            
            if (map[x][i] == 1 && visit[i] == 0)
            {
                //cout << "visit" << i << endl;
                visit[i] = 1;
                q.push(i);
                
            }
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        map[x][y] = map[y][x] = 1;
    }
    dfs(k);
    memset(visit, 0, sizeof(visit));
    cout << endl;
    bfs(k);
    return 0;
}