16947번: 서울 지하철 2호선
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호
www.acmicpc.net
문제 풀이 과정
1. 주어진 노드들로 부터 싸이클을 판별한다.
2. 정점을 돌며 싸이클에 속하는 노드면 0을 출력하고 그렇지 않다면 가장 가까운 싸이클까지의 거리를 출력한다.
싸이클 판별을 어떻게 해야 간단하게 구현할까 생각을 해봤다.
일단 내가 선택한 방법은 dfs의 인자로 (첫 시작노드, 현재 보고있는 노드, 깊이) 를 주었다.
그리고 만약 깊이가 2이상이고 현재 보고있는 노드에 연결된 노드가 첫 시작노드라면 싸이클이라고 판단했다.
만약 싸이클임이 확정이면 cycle이라는 배열에다 dfs로 돌면서 방문한 노드를 추가해 주었다.
시간 효율성이 살짝 부족하지 않았나 생각한다.
'Algorithm' 카테고리의 다른 글
| 프로그래머스 - 신규 아이디 추천 / C++ (0) | 2021.03.03 |
|---|---|
| 백준 - 2146번(다리 만들기) / C++ (0) | 2021.02.27 |
| 프로그래머스 - 키 순서 / C++ (0) | 2021.02.23 |
| 백준 - 1422번(숫자의 신) / C++ (0) | 2021.02.22 |
| 프로그래머스 - 가장 큰 수 / C++ (0) | 2021.02.22 |