[백준/BOJ] gold3 - 16947번 서울 지하철 2호선 (Python)

▶16947 - 서울 지하철 2호선

백준 로고

▶문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

 

▶입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

 

▶출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리,..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

728x90

▶풀이

순환선을 구하기 위해서 dfs, 거리를 구하기 위해서 bfs를 이용했다.

순환선은 a역에서 시작하면 a역으로 돌아와야 한다.

단, a → b → a와 같이 바로 돌아오면 순환역에 해당하지 않는다.

 

다음에 갈 노드가 s이고 cnt가 2보다 크다면 순환선에 해당한다.

그럼 저장해 둔 tmp를 cycle에 넣어주고 check를 True로 해주면 된다.

순환선은 1번만 존재하기에 for문을 종료시키기 위해서 check를 설정해 준 것이다.

 

순환선은 bfs를 할 것도 없이 거리가 0이 된다.

그렇기에 cycle을 이용해서 순환선의 visit를 0으로 해주고, queue에 넣어주면 된다.

그리고 연결된 다른 node들의 cnt는 +1씩 처리하면서 bfs를 돌려주면 된다.

 

from collections import deque
import sys
sys.setrecursionlimit(10**9)


def dfs(s, e, cnt, tmp):
    global check
    for nx in station[e]:
        if nx == s and cnt > 2:
            for t in tmp:
                cycle.append(t)
            check = True

        if visit[nx] == -1:
            visit[nx] = 1
            dfs(s, nx, cnt + 1, tmp + [nx])
            visit[nx] = -1
        

def bfs():
    queue = deque()
    visit = [-1 for _ in range(n + 1)]

    for c in cycle:
        queue.append((c, 0))
        visit[c] = 0

    while queue:
        x, cnt = queue.popleft()

        for nx in station[x]:
            if visit[nx] == -1:
                visit[nx] = cnt + 1
                queue.append((nx, cnt + 1))
    
    return visit


n =  int(input())
station = [[] for _ in range(n + 1)]
visit = [-1 for _ in range(n + 1)]
cycle = []
check = False

for i in range(n):
    a, b = map(int, input().split())
    station[a].append(b)
    station[b].append(a)
                
for i in range(1, n + 1):
    if check == True:
        break
    visit[i] = 1
    dfs(i, i, 1, [i])
    visit[i] = -1

print(*bfs()[1:])

처음에 시간초과가 너무 많이 발생했다.

for문을 처리할 때 break 조건을 걸어주지 않았다.

그래서 이미 순환선을 찾더라도 그 과정을 반복하는 게 문제였다.

그래서 조건을 만들어서 break를 걸어주었더니 통과가 되었다.