백준 16947 서울 지하철 2호선

문제 URL : https://www.acmicpc.net/problem/16947

 

 

문제접근법 : 

양방향 연결 그래프가 주어졌을때 해당 순환선 즉 사이클 노드들이 이루어진 노드들과의 최소거리를

구하는문제입니다.

사이클이 이루어진노드 bfs or dfs 를 이용해서 구하면되지만 이건 dfs를 이용해서 구했습니다.

사이클을 구하는방법은

해당노드에서 다음 방문지점에 부모가 아닌데 방문한적이있고 dfs를 순회할때의 스택안에 존재한다면 그순간 사이클입니다.

scc알고리즘을 공부하신분이라면 쉽게 찾을수 있는 문제이니다.

 

 

 

해당 사이클 노드들을 구한후 사이클 노드들을 기준으로 bfs를 돌아 여러 노드들간의 최소거리만 구하면됩니다.

 

소스코드 : 

import sys
from collections import deque
sys.setrecursionlimit(2000000)
input =sys.stdin.readline
n = int(input())
adj =[[] for i in range(n+1)]
check = [0]*(n+1)
st = []
inst = [0]*(n+1)
cycle = [0]*(n+1)
for i in range(n):
    a,b = map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)


def dfs(cur=1,p = -1):
    check[cur]=1
    inst[cur]=1
    st.append(cur)
    for next in adj[cur]:
        if p == next:
            continue
        if check[next]==0:
            dfs(next,cur)
        elif inst[next]:
            idx = st.index(next)
            for i in range(idx,len(st)):
                cycle[st[i]]=1
    inst[cur]=0
    st.pop()
dfs()

def bfs(cnt):
    q = deque()
    dist=[0]*(n+1)
    for i in range(1,n+1):
        if cycle[i]:
            q.append((i,0))
            check[i]=cnt
    while q:
        cur,dis = q.popleft()
        dist[cur]=dis
        for next in adj[cur]:
            if check[next]!=cnt:
                q.append((next,dis+1))
                check[next]=cnt
    return dist

cnt=2
dist = bfs(cnt)
for i in range(1,n+1):
    print(dist[i],end=' ')
    cnt+=1

 

 

 

궁금한점 혹은 모르는점 논리적인오류등 질문은 언제나 환영입니다.