[Algorithm]Baekjoon 24479번 :: 알고리즘 수업 - 깊이 우선 탐색 1

https://www.acmicpc.net/problem/24479

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
 
int n, m, r, a, b;
vector<vector<int>> graph;
int visited[100001];
int visitedCount = 0;
 
void DFS(int node)
{
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (visited[nextNode] != -1) continue;
        
        visited[nextNode] = ++visitedCount;
        DFS(nextNode);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> r;
 
    graph.resize(n + 1);
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        sort(graph[i].begin(), graph[i].end());
    }
 
    memset(visited, -1, sizeof(visited));
 
    visited[r] = visitedCount = 1;
    DFS(r);
 
    for (int i = 1; i <= n; ++i)
    {
        printf("%d\n", visited[i] != -1 ? visited[i] : 0);
    }
}
 
 

 

 

정답률이 생각보다 낮길래 한번 풀어봤다.

뭘 구해야하는지 이해하면 코드는 어려울게없는데, 나도 문제가 뭘 요구하는지 헷갈리긴 했다.

 

오름차순으로 방문하고, 방문순서를 입력해야 한다.

그래서 간선정보 입력받은다음에 각 노드에대한 간선정보를 정점숫자 기준으로 오름차순을 해줬다.

 

그다음엔 그냥 방문카운트를 전역변수로 두고, 정점을 방문할때마다 방문카운트를 기록해두면 된다.