https://www.acmicpc.net/problem/16947
16947번: 서울 지하철 2호선첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호www.acmicpc.net
존나열심히풀었다. 결국맞았다.
근데 기분이썩는다.
내 풀이방식
그래프를 계속 돌면서, 시작한 위치로 돌아오는 경우(싸이클인 경우)를 찾는다.
찾으면서, 만일 cycle이 아니면 방문처리를 풀고, 맞으면 모두 방문처리한다.
이후, answer을 만들고
순환선에서 밖이랑 연결된 정점은 간선이 3 이상일 것이므로,
내가 찾은 cycle을 돌면서, 간선이 3 이상인 정점을 찾는다.
이 정점에서부턴 트리 구조일 것이므로, 절대 순환되지 않는다.
내가 찾은 정점들로부터, bfs를 돌면서 각 역까지의 거리를 answer[역]에 저장한다.
이러면 answer엔 순환선인곳엔 0, 순환선이 아닌곳엔 각 역까지의 거리가
1번부터 끝번까지 차례대로 저장될 것이다.
print(* answer[1:])을 한다. (처음에 arr을 맞추기위해 일부러 0번 역을 넘었으므로
그니깐 맞아서 행복했다.
시간이 1200초가 걸렸다.
import sysinput=sys.stdin.readlinesys.setrecursionlimit(10**7)
from collections import dequedef dfs(i,last_i,start): # 순환확인 #현재위치,이전위치,시작위치
global flag for j in arr[i]: if j==start and j!= last_i:
flag=True return if not visited[j]:
visited[j]=True dfs(j,i,start) if flag:
return visited[j]=False return
s=deque()def bfs(i): s.append((i,0)) while s: tmp,v=s.popleft()
for i in arr[tmp]: if not visited[i]:
visited[i]=True s.append((i,v+1))
answer[i]=v+1 n=int(input())
arr=[[]for _ in range(n+1)]visited=[False for _ in range(n+1)]
visited1=[False for _ in range(n+1)]for _ in range(n):
a,b=map(int,input().split()) arr[a].append(b) arr[b].append(a) #입력
flag=Falsefor i in range(1,n+1): visited[i]=True dfs(i,None,i) if flag:
break else: visited[i]=Falseanswer=[0 for _ in range(n+1)]
for i in range(1,n+1): if visited[i] and len(arr[i])>2: bfs(i)
print(* answer[1:])이후, 다른사람들의 풀이를 보는데, 파이썬으로 80초에 푸는 사람이 있더라
코드를 따라 쳐봤는데도, 이해가 안된다.
"""정점의 개수 == 간선의 개수 + 1 이면 트리 형태이다.트리 형태에서 간선이 한 개 추가되면 사이클은 단 한 개 존재한다.
사이클 찾기: 임의의 한 정점에서 dfs를 한다.방문한 정점들을 스택에 저장하고, 방문한 적이 있는 정점 X를 방문하게 될 경우
X가 pop될 때까지 현재 스택에 있는 요소들을 pop한 것이 사이클이다."""import sys
sys.setrecursionlimit(int(5e3))def input():
return sys.stdin.readline().rstrip()def main(): n = int(input())
graph = [[] for _ in range(n + 1)] for edge in range(n):
a, b = map(int, input().split()) graph[a].append(b)
graph[b].append(a) visited = [False] * (n + 1) visit_stack = []
def find_cycle(curr_node: int, prev_node: int) -> int:
if visited[curr_node]: return curr_node
visited[curr_node] = True visit_stack.append(curr_node)
for next_node in graph[curr_node]: if next_node != prev_node:
cycle_end = find_cycle(next_node, curr_node)
if cycle_end: return cycle_end
visit_stack.pop() return 0 end_point = find_cycle(1, 0)
cycle_lp = visit_stack.index(end_point)
cycle_set = set(visit_stack[cycle_lp:]) dists = [-1] * (n + 1)
def calc_dist(curr_node: int, prev_node: int, dist: int):
dists[curr_node] = dist for next_node in graph[curr_node]:
if next_node not in cycle_set and next_node != prev_node:
calc_dist(next_node, curr_node, dist + 1)
for node in cycle_set: calc_dist(node, 0, 0) print(*dists[1:])
if __name__ == '__main__': main()