정올 #1912 미로탐색

정올 #1912 미로탐색

벡터와 그래프탐색 DFS를 이용

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m, a, b;
vector<int> adj[100005]; //10만개의 벡터 생성
vector<int> ans;
int chk[100005];
 
 
void dfs(int now){
    if(chk[now]) return; //그 방에 이미 방문했으면 리턴
    chk[now] = 1; //방문하지 않았으므로 방문처리(체크)
    printf("%d ", now); //방문했다고 프린트(정답 형식 참고)
    for(int x : adj[now]){
        dfs(x); //now와 연결된 모든 방에 대해 재귀
    }
}
 
int main(void){
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; i++){
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a); //연결된 방 서로 벡터에 push_back
    }
    for(int i = 1; i<= n; i++){
        sort(adj[i].begin(), adj[i].end()); //내림차순 정렬
    }
    dfs(1);
    for(int x : ans) printf("%d ", x); //ranged-based-for문 이용
    return 0;
}