[백준 16947] 서울 지하철 2호선 (Python)

www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

 

문제풀이

N : 입력값

adj_list : 양뱡향 인접리스트

check : 노드 방문 여부 체크

dist : 최소 방문 거리

 

DFS를 통해 사이클을 찾고, BFS를 통해 특정 노드에서 사이클 까지의 거리를 계산하는 방식으로 해결할 수 있다.

check를 통해 방문한 노드(check[x] = 1), 방문하지 않은 노드(check[x] = 0), 사이클에 속한 노드(check[x] = 2) 구분

sys.setrecursionlimit 을 통해 재귀 깊이를 크게 설정해야 런타임에러가 나지 않는다.

 

1. 사이클 찾기

- DFS를 통해 특정 노드 방문

- 이미 방문한 노드(check[x] == 1 or check[x] == 2)라면 거리차를 구해서, 거리차가 3 이상이라면 사이클에 속한다.

- 사이클에 속한 노드일 경우 check[x] = 2 로 변경

 

2. BFS를 통해 특정 노드에서 사이클 까지의 거리 계산하기

- check[x] == 2 일 경우 사이클에 속한 노드 => dist[x] = 0 로 변경

- check[x] == 1 or check[x] == 0 일 경우 사이클에 속하지 않은 노드 => dist[x] = -1 로 변경

- 노드들을 방문하면서 사이클에 속하지 않은 노드일 경우 dist 갱신

 

코드

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

# DFS를 통해 사이클 찾기

def dfs(x, cnt):
    # 이미 방문한 노드인데 거리차가 3 이상일 경우 사이클
    if check[x]:
        if cnt - dist[x] >= 3:
            return x
        else: return -1
    check[x] = 1
    dist[x] = cnt
    for y in adj_list[x]:
        cycleStartNode = dfs(y, cnt + 1)
        if cycleStartNode != -1:
            check[x] = 2
            if x == cycleStartNode: return -1
            else: return cycleStartNode
    return -1

if __name__ == '__main__':
    N = int(input())
    adj_list = [[] * (N + 1) for _ in range(N + 1)]
    # check[i] = 0 : 방문하지 않은 노드
    # check[i] = 1 : 방문한 노드
    # check[i] = 2 : 사이클에 속하는 노드
    check = [0] * (N + 1)
    dist = [0] * (N + 1)

    for _ in range(N):
        u, v = map(int, sys.stdin.readline().split())
        adj_list[u].append(v)
        adj_list[v].append(u)
    # 사이클 찾기
    dfs(1, 0)
    # BFS를 통해 사이클까지의 거리 계산하기
    q = deque()
    for i in range(1, N + 1):
        if check[i] == 2:
            q.append(i)
            dist[i] = 0
        else:
            dist[i] = -1
    while q:
        x = q.popleft()
        for y in adj_list[x]:
            if dist[y] == -1:
                q.append(y)
                dist[y] = dist[x] + 1
    print(' '.join(map(str, dist[1:])))

 

결과

 

위 풀이는 'webigotr' 님의 C++ 풀이를 참고한 코드입니다.

webigotr.tistory.com/282

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!