[백준/BOJ] 백준 16947번 : 서울 지하철 2호선

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 역들의 관계로 그래프를 만들고, 직전에 방문했던 위치는 방문하지 않는 dfs를 수행하여, SCC(강한 연결 요소)를 만드는 것과 비슷한 방법으로, 사이클에 속한 정점들을 판별했다. 그리고, 각 정점(역)에서 사이클(순환선)까지 최단 거리는 해당 정점에서 사이클까지 bfs(너비 우선 탐색)를 수행하여 문제를 해결했다. 코드 #include #include #include ..

2023.10.18