[Baekjoon] 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 - c++

재우·2022년 6월 25일
0

Baekjoon

목록 보기
1/21
post-thumbnail

문제


문제링크 : https://www.acmicpc.net/problem/24479 (단계별로 풀어보기 : 그래프와 순회)

문제 풀이

dfs의 의사 코드가 문제에 나와 있으므로 문제를 풀기 위해서 dfs를 구현하기 위한 간선 집합과, 방문기록을 위한 정점 집합, 그리고 방문순서를 기록할 집합을 vector형식으로 선언하였다. 그리고 구현하면서 고려했던 부분은 1. 간선입력받으면 양방향간선인것을 생각하고 간선집합을 만들어야 한다. 2."인접 정점은 오름차순으로 방문한다." 고 명시되어 있어 각 graph[i].begin부터 graph[i].end까지 정렬해야 한다. 이렇게 하여 해당 문제는 쉽게 해결할 수 있었고, 문제를 풀면서 벡터 정렬만 다시 리마인드 하였다. 자료형식을 vector로 한 이유는 배열로 선언하였을 때보다 메로리 관점에서 좋다고 생각하고 해당 문제도 정점의 수가 5<=N<=100,000 이므로 배열로 선언하면 아마 메모리 초과가 날 것같다.(정답비율이 낮은이유가 해당 부분일 것 같다)
dfs에 대해서 모른다면 dfs 알고리즘 개념먼저 공부하고 풀어보면 이해하기 좋은 문제일것 같다. 간단히는 dfs란 depth first search, 깊이우선탐색으로 한 정점에서 연결되어 있는 방문하지 않은 정점으로 계속해서 이동하며 만약 연결된 정점이 모두 방문되거나 연결된 정점이 없으면 이전의 정점으로 이동한다(해당 문제에서는 첫방문순서만 생각하면 된다). 그렇게 하여 시작정점에서 이동가능한 정점을 탐색하는 방식이다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector <vector<int>> graph;
vector <int> visited;
vector <int> sequence;
int N, M, R, Seq;

void input();
void dfs(int n);
void sol();

int main()
{   
    fastio;
    input();
    sol();
    return 0;
}

void input()
{
    cin >> N >> M >> R;
    graph.resize(N+1);
    visited.resize(N+1);
    sequence.resize(N+1);
    int u,v;
    for(int i=0; i<M; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for(int i=1; i<=N; i++) sort(graph[i].begin(), graph[i].end());
}

void dfs(int n)
{
    sequence[n] = ++Seq;
    visited[n] = 1;
    int graphsize = graph[n].size(), v;
    for(int i=0; i<graphsize; i++){
        v = graph[n][i];
        if(visited[v]==0) dfs(v);
    }
}

void sol()
{
    dfs(R);
    for(int i=1; i<N+1; i++)    printf("%d\n",sequence[i]);
}

2개의 댓글

comment-user-thumbnail
2022년 6월 26일

너무 똑똑해요!!

1개의 답글