[C/C++] 백준 1260, DFS BFS

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> edge[10001];	//DFS와 BFS에서 같이 사용할 자료구조
int visit[10001];			//DFS와 BFS에서 같이 사용할 자료구조

void initVisit(){	//방문 기록을 0으로 초기화하는 함수
	for(int i=0;i<10001;i++)
    	visit[i]=0;
}

void DFS(int v){
	visit[v]=1;		//해당 정점을 방문한 것으로 표시
    printf("%d ", v);
    for (int i=0; i<edge[v].size();i++){
    	if (visit[edge[v][i]]==0)
        	DFS(edge[v][i]);
    }
}

void BFS(int v){
	int u;
    queue<int> q;
    
    q.push(v);
    visit[v]=1;		//해당 정점을 방문한 것으로 표시
    while(!q.empty()){
    	u=q.front();
        q.pop();
        printf("%d ", u);
        for (int i=0;i<edge[u].size();i++){
        	if (visit[edge[u][i]]==0){
            	visit[edge[u][i]]=1;
                q.push(edge[u][i]);
            }
        }
    }
}

int main(){
	int n, m, s;	//n=정점의 수, m=간선의 수, s=탐색을 시작할 정점
    scanf("%d %d %d", &n, &m, &s);
    int i, u, v;	//정점 u와 v 사이의 연결관계 입력받기
    for (i=0;i<m;i++){
    	scanf("%d %d", &u, &v);
        edge[u].push_back(v);	//무방향 그래프이므로 양쪽 모두에 입력
        edge[v].push_back(u);	//무방향 그래프이므로 양쪽 모두에 입력
    }
    
    for (i=1;i<=n;i++)
    	sort(edge[i].begin(), edge[i].end());	//하나의 정점에 연결된 정점들을 오름차순으로 정렬
    
    initVisit();	//방문 기록 초기화
    DFS(s);
    printf("\n");
    initVisit();	//방문 기록 초기화
    BFS(s);
    
}