백준 1260번 - DFS와 BFS

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

편의상 카테고리에는 BFS로 분류했는데 DFS와 BFS를 모두 사용하는 문제이다.

정점의 개수가 N개일 때, N*N크기의 2차원 인접행렬을 만들 수 있지만 

N개의 정점을 모두 방문할 필요가 없기 때문에, 정점의 번호가 주어질때마다 정점을 추가해주는 인접리스트 방법으로 문제를 풀었다.

주의할 점은 하나의 정점에 추가되는(연결되는) 다른 정점들이 크기순으로 추가되는 것이 아니기 때문에

하나의 정점에 연결된 다른 정점들을 크기 순으로 총 N번 정렬해줘야 한다.

이는 문제에 나와있는 예제입력2를 확인해보면

시작 정점인 3번 정점에 4번 정점과 1번 정점순으로 연결되도록 입력을 받는데

이를 다시 1번, 4번 정점순으로 연결되어 있도록 정렬 해주면 크기순으로 방문을 하게 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int N,M,V;
vector<int> edge[1001];
vector<int> visited;
 
void dfs(int node){
    
    printf("%d ",node);
 
    for(int i=0;i<edge[node].size();i++){
        if(!visited[edge[node][i]]){
            visited[edge[node][i]]++;
            dfs(edge[node][i]);
        }
    }
    
}
 
void bfs(){
    
    queue<int> q;
    q.push(V);
    
    visited[V]=1;
    while(!q.empty()){
        int node=q.front();
        q.pop();
        
        printf("%d ",node);
        for(int i=0;i<edge[node].size();i++){
            if(!visited[edge[node][i]]){
                visited[edge[node][i]]++;
                q.push(edge[node][i]);
            }
        }
    }
}
int main(){
    
    cin>>N>>M>>V;
    
    int node1,node2;
    visited = vector<int> (N+1,0);
    for(int i=0;i<M;i++){
        scanf("%d %d",&node1,&node2);
        edge[node1].push_back(node2);
        edge[node2].push_back(node1);
    }
    
    //인접리스트 정렬
    for(int i=1;i<=N;i++)
        sort(edge[i].begin(),edge[i].end());
    
    //dfs
    visited[V]=1;
    dfs(V);
    printf("\n");
    
    //bfs
    visited = vector<int> (N+1,0);
    bfs();
    
    return 0;
}