화투의 개발 블로그

[문제 링크]

DFS 문제다. 각 방이 노드, 문이 간선인 무방향 그래프로 보고 DFS로 방문하며 출력을 하면 된다.

나는 인접리스트로 문제를 풀었는데,(인접배열로 하기엔 배열의 크기가 너무 크다.)

가장 낮은 번호의 방을 먼저 방문한다고 했으므로, 인접리스트를 정렬 한 뒤에 탐색을 진행하도록 하였다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<vector<int> > graph;
vector<int> visited;
void dfs(int cur){
    printf("%d ",cur);
    sort(graph[cur-1].begin(),graph[cur-1].end());
    for(int i =0; i<graph[cur-1].size();i++){
        if(visited[graph[cur-1][i]-1]==0){
            visited[graph[cur-1][i]-1] = 1;
            dfs(graph[cur-1][i]);
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    graph.resize(n);
    visited.resize(n);
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a-1].push_back(b);
        graph[b-1].push_back(a);
    }
    visited[0] = 1;
    dfs(1); 
}