반응형
https://www.acmicpc.net/problem/24479
24479번: 알고리즘 수업 - 깊이 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양
www.acmicpc.net
소스코드
풀이
★ 전형적인 DFS 문제입니다. 한가지 주의해야 할 점이 있다면 방문하는 정점을 출력하는 것이 아닌, 정점을 방문하는 순서 즉, 방문 순서를 출력해야 합니다 !
★ 양방향 간선이 주어졌기 때문에 for문을 사용하여 정점에서 정점으로 이동하는 모든 경우를 확인해줍니다.
★ 정점을 방문할 때는 오름차순으로 방문해야 하기에 각각의 정점을 정렬해줍니다.
★ 이후 visited 배열을 확인하며 DFS를 수행하는데, cnt (방문 순서) 변수를 통해 정점에 방문할 때마다 cnt를 1부터 1씩 증가시킵니다.
★ cnt는 a 배열에 기록되는데, a 배열은 정점의 방문 순서를 기록하는 배열입니다 !
★ 이후 1부터 n+1일까지의 정점의 방문순서를 순서대로 출력해줍니다 :)
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 14940번: 쉬운 최단거리 (Python, BFS) (0) | 2023.10.23 |
|---|---|
| [백준 알고리즘] 1253번: 좋다 (Python) (1) | 2023.10.23 |
| [백준 알고리즘] 1431번: 시리얼 번호 (Python) (1) | 2023.10.20 |
| [백준 알고리즘] 8979번: 올림픽 (Python) (0) | 2023.10.20 |
| [백준 알고리즘] 18870번: 좌표 압축 (Python) (0) | 2023.10.20 |