[백준 16947번] 서울 지하철 2호선 - 파이썬

 

① 문제 링크

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

16947번: 서울 지하철 2호선

---

② 알고리즘 분류

그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색

---

③ ★문제풀이 Point★

- 순환선에 속하는 역은 깊이 우선 탐색(dfs) 실시

- 각 역과 순환선 사이의 거리는 너비 우선 탐색(bfs) 실시

---

④ 풀이

이 문제는 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구하는 문제다.

1. 순환선에 속하는 역 구하기

각 역과 순환선 사이의 거리를 구하기 전 먼저 해야 할 일은 순환선에 속하는 역을 구하는 것이다. 

이는 DFS 알고리즘을 이용해 만든다.

순환역이 되기 위한 조건을 살펴보자.

- 시작 역에서 연결된 역을 타고 가다가 다시 시작 역으로 돌아와야 순환역에 해당한다.

ex) 1번째 역 -> 2번째 역 -> 3번째 역 -> 1번째 역 (O)

=> 1. 시작 역 start과 현재 역 idx이 일치하다면 순환역에 해당한다.

여기서 주의할 점은 하나의 역만 갔다가 다시 자기 자신의 역으로 돌아오는 경우는 순환역에 해당하지 않는다.

ex) 10번째 역 -> 11번째 역 -> 10번째 역 (X)

=> 2. 방문 횟수 cnt를 설정하여 두 번 이상 다른 역 방문 cnt >= 2 할 시 순환역에 해당한다.

이 2가지를 묶어 순환역이 될 조건을 만들어보면

"시작 역 start == 현재 역 idx" and " 두 번 이상 다른 역 방문 cnt >= 2"이다.

 

2. 역과 순환선 사이의 최소 거리 구하기

먼저 순환선에 속하는 역은 거리를 모두 0으로 처리한다.

순환선에 속하지 않는 역은 bfs를 이용하여 방문한 적이 없는 역들만 방문하면서 check[now] + 1 다음 역을 구한다.

 

참고)

재귀의 깊이가 너무 깊게 간다면 런타임 에러 (RecursionError)를 범할 수 있으므로 재귀의 범위를 임의로 정해준다.

sys.setrecursionlimit(100000)

---

⑤ 코드

다음 코드는 Python3로 작성하였습니다.

# 16947번 서울 지하철 2호선

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)

# 순환선이 존재하는지 확인하는 함수
def circulation_station(start, idx, cnt):
    global cycle
    # 방문한 역이 2곳 이상이고, 현재 역이 시작 역으로 돌아온다면
    if start == idx and cnt >= 2:
        # 순환선으로 표시
        cycle = True
        return
    # 현재 역 방문 표시
    visited[idx] = True
    # 다음 방문할 역을 받으면서
    for i in info[idx]:
        # 아직 방문하지 않은 역이라면
        if not visited[i]:
            # 해당 역을 추가하고 재귀적으로 호출
            circulation_station(start, i, cnt + 1)
        # 이미 방문한 역이며 방문한 역이 2곳 이상이라면
        elif i == start and cnt >= 2:
            # 방문하는 역을 그대로 재귀적 호출
            circulation_station(start, i, cnt)

# 역과 순환역 사이의 거리를 확인하는 함수
def distance_station():
    global check
    q = deque()
    # 순환역에 속하는 역은 모두 거리가 0
    for i in range(n):
        if cycle_station[i]:
            check[i] = 0
            q.append(i)
    # 큐가 빌 때까지 반복
    while q:
        # 현재 역
        now = q.popleft()
        # 다음 역 선택
        for i in info[now]:
            # 역이 순환선에 포함되지 않는 역이라면
            if check[i] == -1:
            	# 큐에 추가
                q.append(i)
                # 이동 거리 구하기
                check[i] = check[now] + 1
    # 모든 각 역과 순환선 사이의 최소 거리 출력
    for i in check:
        print(i, end=' ')

# 역의 개수 입력받기
n = int(input())
# 역과 역을 연결하는 구간의 정보
info = [[] for _ in range(n)]
# 순환역을 표시하는 전체 역
cycle_station = [False] * n
# 정답 변수
check = [-1] * n

# 역 구간 정보 입력받기
for _ in range(n):
    a, b = map(int, input().split())
    info[a-1].append(b-1)
    info[b-1].append(a-1)

# 순환선 확인
for i in range(n):
    # 방문 여부 표시 리스트
    visited = [False] * n
    # 순환선이 있는지 여부
    cycle = False
    # 순환선 탐색
    circulation_station(i, i, 0)
    # 순환선이 있다면 순환선에 속하는 역을 순환역으로 표시
    if cycle:
        cycle_station[i] = True

# 역 거리 확인
distance_station()

---

16947 파이썬 채점 결과

 

백준 16947번 서울 지하철 2호선

---

⑥ 마치며

이번 문제는 dfs와 bfs를 이용해서 차근차근 해결해야 하는 문제였다. 

필자는 문제를 보고 해결해야 하는 과정을 다음과 같이 생각해보았다.

1. 순환역에 해당하는 역 표시(dfs)

2. 각 역과 순환선 사이의 최소 거리 구하기(bfs)

풀이 과정과 필자의 생각이 정확히 일치했지만 막상 코드로 구현하는데 어려움이 있었다.

처음 풀었을 때 구글링을 통해 조금 더 코드를 보완하였고, 앞으로 더 많은 문제를 접해보면서 실력을 키워나가야겠다.