[백준] 16947. 서울 지하철 2호선 풀이 (Python, JavaScript)

16947번: 서울 지하철 2호선

16947. 서울 지하철 2호선

접근한 방법

그래프에 존재하는 사이클까지 각 노드가 도달가능한 최소 거리를 구하는 문제입니다.

두 가지 과정이 필요합니다.

1. 사이클 그래프 찾기

2. 사이클 그래프로부터 각 노드 도달거리 탐색하기

 

1번에서는 DFS로 사이클이 나올때까지 탐색합니다. 사이클을 찾는 방법은 탐색 출발 노드와 다음 탐색 노드가 같은 경우를 찾으면 됩니다. 단 사이클은 노드가 3개 이상이어야 하므로 깊이가 3회이상인 경우에만 종료할 수 있도록 합니다. 그 외에는 보편적인 DFS 코드와 같고 사이클을 발견하면 나머지 노드들을 탐색하지 않고 바로 종료할 수 있도록 합니다. 그렇지 않으면 이 문제의 컴파일러에서는 시간 초과가 발생합니다.

 

2번에서는 BFS로 사이클 그래프들을 이루고 있는 노드로부터 주변 노드를 탐색합니다. 방문하지 않은 노드들만 탐색하여 깊이를 체크해주면 도달 거리를 기록할 수 있습니다.

 

Python

import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n + 1)]
cycle = [3000] * (n + 1) # 사이클까지 각 노드의 도달 거리
for _ in range(n):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0] * (n + 1)
finded = 0
def find_cycle(d, cnt): # 지나온 노드, 깊이
    global finded
    if finded: # 발견한 경우 시간 단축을 위해 중단
        return
    # 현재 노드와 연결된 노드 탐색
    for i in graph[d[-1]]: 
        if i == d[0] and cnt >= 2: # 사이클인 경우 종료
            for j in d:
                cycle[j] = 0 # j노드는 사이클에 속하는 노드
            finded = 1
            return
        if not visited[i]:
            visited[i] = 1
            find_cycle(d + [i], cnt + 1)
            visited[i] = 0

for i in range(1, n + 1):
    visited[i] = 1
    find_cycle([i], 0)
    visited[i] = 0

# 사이클에 속하는 노드로부터 BFS탐색
from collections import deque
q = deque()
for i in range(1, n + 1): 
    if cycle[i] == 0:
        q.append((i, 0))
while q:
    now, d = q.popleft()
    for v in graph[now]:
        if cycle[v] == 3000: # 방문하지 않은 경우 거리 기록
            cycle[v] = d + 1
            q.append((v, d + 1))
print(*cycle[1:])

JavaScript

function solution(n, list) {
  const graph = Array.from({ length: n + 1 }, () => []);
  const cycle = Array(n + 1).fill(3000);
  const visited = Array(n + 1).fill(0);
  let finded = 0;

  list.forEach((v) => {
    graph[v[0]].push(v[1]);
    graph[v[1]].push(v[0]);
  });

  const findCycle = (passed) => {
    if (finded) return;
    for (const v of graph[passed[passed.length - 1]]) {
      if (v === passed[0] && passed.length >= 3)
        return (finded = 1 && passed.forEach((p) => (cycle[p] = 0)));
      if (!visited[v]) {
        visited[v] = 1;
        findCycle(passed.concat(v));
        visited[v] = 0;
      }
    }
  };

  for (let i = 1; i <= n; i += 1) {
    if (!finded) {
      visited[i] = 1;
      findCycle([i]);
      visited[i] = 0;
    }
  }
  let [q, front] = [[], 0];
  for (let i = 1; i <= n; i += 1) if (!cycle[i]) q.push([i, 1]);
  while (front <= q.length - 1) {
    let [now, d] = q[front++];
    for (const v of graph[now]) {
      if (cycle[v] === 3000) {
        cycle[v] = d;
        q.push([v, d + 1]);
      }
    }
  }
  return cycle.slice(1);
}

solution(12, [[1, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 4], [2, 3], [7, 9], [9, 12], [7, 10], [10, 11],])