정올 #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;
}
Author And Source
이 문제에 관하여(정올 #1912 미로탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cirtuare/정올-1912-미로탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)