#include<iostream>
#include<queue>
using namespace std;
bool check[1001];
int a[1001][1001];
int n, m;
void dfs(int x){ //x를 방문한다.
check[x] = true; //x를 방문처리하고
printf("%d ", x); //x를 출력
for(int i=1; i<=n; i++){ // i를 처음부터 끝까지 순회하는데
if(a[x][i] == 1 && check[i] == false){ //x에서 i로 가는 간선이 있고, i를 방문하지 않았다면
dfs(i); //i를 방문한다.
}
}
}
int main(){
int v;
cin>>n>>m>>v;
while(m--){
int p, q;
cin>>p>>q;
a[p][q]=1;
a[q][p]=1;
}
dfs(v);
cout<<'\n';
for(int i=0; i<1001; i++){
check[i] = false;
}
queue<int> q; //큐를 생성하고
check[v]=true; //지금 있는 곳을 방문처리 하고
q.push(v); // 큐에 삽입한 후
while(!q.empty()){ // 큐가 빌때까지
int y = q.front(); // 지금 있는 곳을 적어놓은 다음
q.pop(); //큐를 pop한 후
printf("%d ",y); // y를 출력하고
for(int i=1; i<=n; i++){ //연결되어 있는 간선을 찾기위해
if(a[y][i] == 1 && check[i] == false){ //y에서 i로 가는 간선이 있고 i를 방문하지 않았다면
check[i]=true; // 방문처리하고
q.push(i); //i를 큐에 삽입한다.
}
}
}
return 0;
}
문제 출처 : https://www.acmicpc.net/problem/1260
'코딩스터디' 카테고리의 다른 글
JavaScript로 이진 탐색(Binary Search) 알고리즘 구현하기 (0) | 2023.07.13 |
---|---|
JavaScript로 스택(Stack) 구현하기 (0) | 2023.07.13 |
백준[브루트포스] 일곱난쟁이 문제 (0) | 2019.09.20 |
최소공배수 LCM 구하기 (0) | 2019.09.20 |
최대공약수와 유클리드 호제법 (0) | 2019.09.20 |