풀이
입력받은 양방향 그래프에 대해 정점 K부터 시작해 연결된 정점 중 번호가 작은 정점을 우선적으로 방문하는 문제다.
이미 방문한 정점을 다시 방문해서는 안되며, self-loop는 존재하지 않는다.
번호가 작은 정점을 우선적으로 방문하므로 미리 정렬해주자.
dfs를 loop로 구현했다.
정점K부터 시작해 방문한 모든 정점을 방문표시해주며, 현재 정점과 연결된 반대 정점 중 방문하지 않은 정점에 대해 탐색하는 방법이다.
만약 더 이상 다른 정점으로 방문이 불가능한 경우 loop를 빠져나오며, 지금까지 방문한 정점의 갯수와 마지막으로 방문한 정점의 번호를 출력하면 된다.
출처
구름LEVEL
난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.
level.goorm.io
'PS' 카테고리의 다른 글
| [구름톤 챌린지] 16일차 - 연합 [Python] (0) | 2023.09.06 |
|---|---|
| [구름톤 챌린지] 15일차 - 과일구매 [Python] (0) | 2023.09.02 |
| [구름톤 챌린지] 13일차 - 발전기 (2) [Python] (0) | 2023.08.31 |
| [구름톤 챌린지] 12일차 - 발전기 [Python] (0) | 2023.08.29 |
| [구름톤 챌린지] 11일차 - 통증 (2) [Python] (0) | 2023.08.29 |