둠치킨
코딩하는 둠치킨
둠치킨

블로그 메뉴

  • 홈
  • 분류 전체보기 (225) N
    • 프로그래머스 (1) N
      • 해시 (1) N
    • BOJ (176)
      • 스택 (14)
      • 큐 (5)
      • 덱 (4)
      • 그래프 (31)
      • 배열 (8)
      • 재귀 (12)
      • 브루트 포스 (2)
      • 그리디 알고리즘 (7)
      • 다이내믹 프로그래밍 (14)
      • 백트래킹 (24)
      • 기하학 (4)
      • 트리 (4)
      • 구현 (14)
      • 수학 (3)
      • 맵 (1)
      • 다익스트라 (2)
      • 누적합 (5)
      • 유니온 파인드 (1)
      • 분할 정복 (2)
    • 자료구조 (15) N
      • 스택 (3)
      • 큐 (5)
      • 덱 (2)
      • 그래프 (1)
      • 트리 (2) N
      • 힙 (1)
      • 정렬 (1)
    • C++ (11)
      • 모두의코드 (2)
      • Effective C++ (3)
      • C++ STL (6)
    • 컴파일러 (1)
    • OS (17)
    • 컴퓨터 구조 (2)
    • Unreal Engine 5 (2)

공지사항

전체 방문자
오늘
어제

인기 글

최근 글

태그

  • BFS
  • boj
  • Bruteforce
  • C
  • C++
  • C++ STL
  • Cache Memory
  • deadlock
  • DFS
  • Effective C++
  • java
  • Mutex
  • next_permutation
  • os
  • Process
  • rotate
  • semaphore
  • spin lock
  • STL
  • STL C++
hELLO · Designed By 정상우.
둠치킨

코딩하는 둠치킨

BOJ

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

2024. 9. 30. 00:14

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

사용 언어: C++

 

풀이

무방향 그래프이므로 양쪽 인덱스에 넣어주고, 시작 노드부터 dfs를 돌린다.

dfs에서는 visited를 true로 해주고, 방문한 노드의 순서를 order로 저장하고, 오름차순 방문이므로 sort를 하고 다음 인접 노드가 방문하지 않은 노드면 재귀를 돌린다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> graph[100001];  
bool visited[100001];       
int order[100001];          
int cnt = 1;                

void dfs(int node) 
{
    visited[node] = true;
    order[node] = cnt++;
    
    sort(graph[node].begin(), graph[node].end());
    
    for (int neighbor : graph[node]) 
    {
        if (!visited[neighbor]) 
        {
            dfs(neighbor);
        }
    }
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M, R;
    cin >> N >> M >> R;

    for (int i = 0; i < M; i++) 
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dfs(R);

    for (int i = 1; i <= N; i++) 
    {
        if (visited[i]) 
        {
            cout << order[i] << "\n";
        } else 
        {
            cout << 0 << "\n";
        }
    }

    return 0;
}
저작자표시 (새창열림)

'BOJ' 카테고리의 다른 글

24444번: 알고리즘 수업 - 너비 우선 탐색 1  (0) 2024.09.30
24480번: 알고리즘 수업 - 깊이 우선 탐색 2  (0) 2024.09.30
1654번: 랜선 자르기  (0) 2024.09.27
2110번: 공유기 설치  (0) 2024.09.27
11650번: 좌표 정렬하기  (1) 2024.09.26
    'BOJ' 카테고리의 다른 글
    • 24444번: 알고리즘 수업 - 너비 우선 탐색 1
    • 24480번: 알고리즘 수업 - 깊이 우선 탐색 2
    • 1654번: 랜선 자르기
    • 2110번: 공유기 설치
    둠치킨
    둠치킨
    코딩 공부를 위한 코딩 블로그 기록 일기

    티스토리툴바