[BOJ/백준] 16947. 서울 지하철 2호선 (python)

https://www.acmicpc.net/problem/16947

Problem

역의 개수와 연결되어 있는 역(구간)의 정보를 알려주면 순환역을 구하고, 각 역에서 순환역 사이의 거리를 구해 사이의 거리 출력하는 문제

Solution

크게 두가지 단계로 나누었다.

1. 순환역인지 판단 (dfs)

2. 각 역에서 순환역까지의 거리 (bfs)
   ​

1(순환역인지 판단)의 함수를 구현하려면 연결된 역을 타고 점점 가다가 자기자신으로 되돌아오면 순환역으로 인식하면 된다.

때문에, 주의할 점은 방문한 역이라고 무시하고 무조건 다음 역으로 넘어가지 않아야 한다.

또한, "1역 -> 2역 -> 1역" 과 같이 하나의 역만 갔다가 다시 자신의 역으로 되돌아 온 경우를 순환역이라고 인식하지 않게 처리해야한다.

"현재역==시작역 and 두번이상 다른 역 방문" 이라는 조건을 만족하면 순환역이라고 표시해주었다.
​

2(각 역에서 순환역까지의 거리)의 함수를 구현하기 위해서는 순환역에 속하는 역은 거리를 모두 0으로 저장해준다.

순환역에 속하지 않는 역은 방문한 적이 없는 역들만 방문하면서 (연결 기준)현재 역의 거리 + 1을 해주어 다음 역에 저장해준다. 이 때는 deque를 이용한다.
​

주의할 점

실행시키면 결과는 아무 문제없이 나오는데 백준에 제출하면 계속해서 런타임에러가 나서 검색해보니 가끔 재귀의 깊이가 너무 깊이까지 가게되면 런타임 에러가 발생할 수 있다고 한다.

그럴 때는 sys.setrecursionlimit(100000)

Python Code