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

 

이해가 잘안됐는데 좀 보다보니 이해됐다

 

사각형 부분을 순환선이라고 하고

삐져나온 부분을 지선이라고 하는것이다.

 

그럼 이제 순환 노선인걸 어떻게 알아내는걸까

 

순환노선인걸 알아내기만 하면 bfs로 최단경로 구해주면 될거같고

 

연결된 노드로 갈수있는 연결된 간선이 아닌 다른 간선을 통해서 들어갈수있는 경우 순환노드로 취급하면 될거같다.

dfs를 이용해서 작성하면 될거같다. 단 부모정점은 제외한다

 

 

 

import sys

n=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n)]
for _ in range(n):
    v1,v2=map(int,sys.stdin.readline().rstrip().split())
    graph[v1-1].append(v2-1)
    graph[v2-1].append(v1-1)

check_circle=[0]*n

def dfs(start,p):
    if visited[start]==1:
        check_circle[start]=1
        return
    visited[start]=1
    for i in graph[start]:
        if i!=p:
            dfs(i,start)

for i in range(n):
    visited=[0]*n
    dfs(i,i)
print(1)

 

1차로 순환노드를 구하기까지 했다.

 

이제 bfs를 써서 순환노드까지의 최단거리를 구하면 된다.

from collections import deque
import sys

n=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n)]
for _ in range(n):
    v1,v2=map(int,sys.stdin.readline().rstrip().split())
    graph[v1-1].append(v2-1)
    graph[v2-1].append(v1-1)

check_circle=[0]*n

def dfs(start,p):
    if visited[start]==1:
        check_circle[start]=1
        return
    visited[start]=1
    for i in graph[start]:
        if i!=p:
            dfs(i,start)

def bfs(start):
    q=deque()
    visited=[0]*n
    q.append([start,0])
    visited[start]=1
    while q:
        cur_v,deep=q.popleft()
        if check_circle[cur_v]==1:
            print(deep,end=' ')
            return
        for i in graph[cur_v]:
            if visited[i]==0:
                q.append([i,deep+1])
                visited[i]=1

for i in range(n):
    visited=[0]*n
    dfs(i,i)

for i in range(n):
    bfs(i)

디버깅이 너무 오래걸린다. 한번에 잘 작성해야하는데 숙련도 부족으로 쉽지않다

 

재귀제한은 3000으로 풀어야한다

from collections import deque
import sys

sys.setrecursionlimit(5000)

n=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n)]
for _ in range(n):
    v1,v2=map(int,sys.stdin.readline().rstrip().split())
    graph[v1-1].append(v2-1)
    graph[v2-1].append(v1-1)

check_circle=[0]*n

def dfs(start,p):
    if visited[start]==1:
        check_circle[start]=1
        return
    visited[start]=1
    for i in graph[start]:
        if i!=p:
            dfs(i,start)

def bfs(start):
    q=deque()
    visited=[0]*n
    q.append([start,0])
    visited[start]=1
    while q:
        cur_v,deep=q.popleft()
        if check_circle[cur_v]==1:
            print(deep,end=' ')
            return
        for i in graph[cur_v]:
            if visited[i]==0:
                q.append([i,deep+1])
                visited[i]=1

for i in range(n):
    visited=[0]*n
    dfs(i,i)

for i in range(n):
    bfs(i)

 

휴

 

풀고나서 채점현황을 좀 봤는데 다들 너무 속도가 빨라서 풀이를 좀 찾아봤는데 순환선은 한개만 존재한다고 한다. 도대체 그런조건이 어디있는거지? 아무튼 그러면 dfs를 수정하면 훨씬 빨라진다. 근데 그런 조건이 문제에는 안써있는데...

 

잘만 써있었다.