[백준] 16947 :서울 지하철 2호선

DFS + BFS

문제: 서울 지하철 2호선

개인적으로 아주 좋은 문제라고 생각합니다.
DFS와 BFS를 어떨 때 써야하는지 잘 알 수 있는 문제입니다.

저번에 풀었던 Two-Dots문제를 활용하여 DFS로 사이클 여부를 판단하고
사이클이 아닌 노드들은 BFS를 이용하여 순환선까지의 가장 짧은 거리를 출력합니다 .

이 문제에서 사이클이 형성되는 조건은,
1. 시작점과 끝점이 같다.
2. cnt가 2이상이다 (0부터 시작)
여기서 1-2-1 처럼 다시 돌아오는 것을 세는 일이 없도록 방문배열도 만들어줍니다.
이렇게 dfs로 cycle인 노드들을 구분해주고 bfs로 cycle인 노드들을 큐에 하나씩 넣어주며 사이클이 아닌 노드의 값을 더해가며 구해줍니다.
그리고 마지막에는 답이 저장된 check 배열을 출력해주면 됩니다.

import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
# for cycle : 값이 0인것들
isCycle = [False]*(n+1)
# not for cycle : BFS 돌리면서 값 증가할 것  
isCheck = [False] * (n+1)
check = [-1] * (n+1)
# 사이클을 찾을 때 쓰임 
def dfs(start, end, cnt):
	global cycle
	if cycle:
		return
	# 종료조건 : 시작점과 끝점이 같고 , 방문한 점이 2개 이상이다 
	if start == end and cnt >= 2:
		cycle = True
		return
	# 현재지점 방문처리 
	visited[end] = True
	# 현재노드와 연결된 노드 순회 
	for i in graph[end]:
		# 역으로 돌아가지 않게 하기 위함 ex) 1-2-1
		if not visited[i]:
			dfs(start, i, cnt+1)
		# 종료조건에 닿으면 갯수 증가 시키지 않고 dfs 
		if i == start and cnt >= 2:
			dfs(start, i, cnt)
	return
# 사이클이 아닌 노드의 값을 계산하기 위해 쓰임 
def bfs():
	q = deque()
	# 사이클이면 값이 0이고 이것을 큐에 넣음 (방문처리 해야함)
	for i in range(1, n+1):
		if isCycle[i]:
			check[i] = 0
			q.append(i)
			isCheck[i] = True
	while q:
		x = q.popleft()
		# 관련 노드 순회 
		for v in graph[x]:
			# 방문하지 않았으면 방문 처리후에  값을 1증가 시킨 후에 큐에 넣음 
			if check[v] == -1:
				isCheck[v] = True
				check[v] = check[x] + 1
				q.append(v)
	# 답 출력
	for i in range(1, n+1):
		print(check[i], end = ' ')
# 양방향 간선 , 그래프 추가 
for i in range(n):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
#노드를 순회할 때 마다 방문여부와 사이클 초기화 
for i in range(1, n+1):
	visited = [False] * (n+1)
	cycle = False
	dfs(i, i, 0)
	# 해당 노드가 사이클이면 True
	if cycle:
		isCycle[i] = True
# 사이클이 아닌 노드의 값을 출력할 때  쓰임 
bfs()