💡 문제
서울 지하철 2호선은 다음과 같이 생겼다.
지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.
지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.
입력
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
출력
총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.
💭 접근
이 문제는 DFS와 BFS를 한번에 사용해야하는 문제이다. DFS는 순환선을 찾는데에, BFS는 각 역과 순환선 사이의 거리를 구하는데에 사용한다.
- 우선, 순환선을 확인하기 위해 cycle (순환선인지 아닌지 저장되어있는 배열) 이 False인 모든 정점을 시작 정점으로 DFS를 호출한다.
visited = [False for _ in range(n + 1)]
for i in range(1, n + 1):
if not cycle[i]:
first = i
visited[first] = True
dfs(first, 0)
visited[first] = False- 16929번 Two Dots 문제와 같이 사이클을 만들 수 있는지 먼저 확인한다. 이때 다음 정점에 시작 정점이 들어가 있는지 확인하면 되는데, 이때 시작 정점 바로 다음 정점은 반드시 시작 정점이 반드시 포함되어 있기 때문에 최소 1개 이상의 정점을 거쳤는지 확인해야한다.
if first in graph[start] and depth > 1:
cycle[first] = True
cycle[start] = True # 시작 정점을 포함하고 있으면 해당 정점도 순환선이므로
return- DFS를 통해 순환선과 지선을 구분하였으면 각 순환선에 포함되어 있는 역을 기준으로 각 지선까지의 거리를 구하기 위해 deque에 순환선에 포함되어 있는 역을 모두 저장한다.
# 순환역에 속하는 역은 모두 거리를 0으로 저장
# 순환역을 기준으로 검사하기 위해 큐에 모두 먼저 넣기
for i in range(1, n + 1):
if cycle[i]:
q.append(i)- 이후 cycle 배열에 False로 저장되어 있는 정점 (지선에 속하는 역) 이 있다면 거리를 더해준다.
while q:
x = q.popleft()
for next in graph[x]:
# 만약 연결되어 있는 곳이 False (지선) 이라면
if not cycle[next] and ans[next] == 0:
ans[next] = ans[x] + 1
q.append(next)📒 코드
# 1. dfs로 순환선을 찾아서 순환선이면 cycle 배열에 True로 저장
# 2. bfs로 각 지선에서 가장 가까운 순환선까지의 거리 저장
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def dfs(start, depth): # 1
if first in graph[start] and depth > 1:
cycle[first] = True
cycle[start] = True
return
for next in graph[start]:
if not visited[next]:
visited[next] = True
dfs(next, depth + 1)
visited[next] = False
def bfs(): # 2
q = deque()
# 순환역에 속하는 역은 모두 거리를 0으로 저장
# 순환역을 기준으로 검사하기 위해 큐에 모두 먼저 넣기
for i in range(1, n + 1):
if cycle[i]:
q.append(i)
while q:
x = q.popleft()
for next in graph[x]:
# 만약 연결되어 있는 곳이 False (지선) 이라면
if not cycle[next] and ans[next] == 0:
ans[next] = ans[x] + 1
q.append(next)
n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
cycle = [False for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
for i in range(1, n + 1):
if not cycle[i]:
first = i
visited[first] = True
dfs(first, 0)
visited[first] = False
ans = [0 for _ in range(n + 1)]
bfs()
print(*ans[1:])
💭 후기
문제 풀이에 성공하고 DFS와 BFS에 기본적인 개념은 생긴 것 같아 뿌듯했던 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/16947
