[BOJ][Python] 백준 20530 번: 양분

1일 1PS 75일차!

📚 문제

---

[골드 1] - 양분

💡 풀이 과정

---

• 효율성이 중요시되는 문제이다.
• 문제는 사이클이 존재하지 않는 트리 구조에서 1개의 간선이 추가되어 사이클이 발생하게 된다.
• 여기서 두 개의 정점을 선택했을 때 해당 정점이 사이클을 기준으로 분리되어있으면 2개의 단순 경로가 존재한다.
• 따라서 사이클을 검출하고 두 개의 정점 분리 여부를 검사하는 것이 문제이다.

• 가장 먼저 사이클을 검출한다.
• 기존 모든 경로를 저장해 한 번에 사이클 전체를 반환하는 함수를 생성했다. 하지만 많은 재귀에 경로 자체를 넣는 것은 시간 초과가 발생한다.
• 그렇기에 마지막 간선의 노드만 반환했다.
  • 1 -> 2 -> 3 -> 4-> 2 로 진행되어 사이클이 검출되었을 때,
  • findCycle() 에서 반환되는 값은 [4, 2] 이다.
  • 이를 이용하기 위해 DFS 를 진행하면서
    • parent = [0, 1, 2, 3, …]
    • 위와 같이 부모 노드를 저장한다.
  • 이후 [4, 2] 를 사용해 사이클 노드 전체를 검출할 수 있다.

• 이후 사이클에 존재하는 노드들을 부모 노드로 지정하고 사이클 외 노드들에 대해서 부모 노드를 최신화한다.

• 이후 쿼리에 대해 같은 부모를 가지면 1, 다르면 2를 출력한다.

📌포인트

---

• visited
  • DFS 를 진행할 때, dfs(now, prev) 를 사용한다면 visited 없이 dfs 를 진행할 수 있다.
  • 하지만 대부분의 경우 visited 를 사용하는 것이 효율적이라 한다.
• cycles
  • DFS 를 진행할 때, 사이클 노드들을 미리 visited 로 설정해 이동 방향을 제한한다.

💻 코드

---

import sys

input = sys.stdin.readline

#RecuresionError 발생 제거..
sys.setrecursionlimit(1000000000)

# 사이클을 검츌하는 함수
def findCycles(now, prev):
    for node in graph[now]:
        if node == prev:
            continue

        # 만약 이미 부모가 최신화 되었다면 해당 간선으로 사이클이 만들어진다.
        if visited[node]:
            return [node, now]
        # 사이클이 만들어지기 이전까지는 간선의 부모 자식 관계를 계속 기록한다.
        else:
            visited[node] = True
            parent[node] = now
            result = findCycles(node, now)
            # 사이클이 검출되었다면 return
            if result:
                return result
    return 0


# 사이클에 존재하는 노드들을 기준으로 그룹화
def dfs(now, p):
    for node in graph[now]:
        if not visited[node]:
            visited[node] = True
            parent[node] = p
            dfs(node, p)


N, M = map(int, input().split())

# 부모와 그래프
parent = [i for i in range(N + 1)]
graph = {}

for i in range(N):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []

    graph[a].append(b)
    graph[b].append(a)


# 사이클 검출
visited = [False for i in range(N + 1)]
visited[1] = True
a, b = findCycles(1, 0)

# 검출된 사이클은 ex)  1-2-3-4 에서 4 -> 2 의 간선을 나타낸다.
# 2 -> 3 -> 4 는 parent 를 통해 따라갈 수 있다.
cycles = [a]
visited = [False for i in range(N + 1)]
visited[a] = True

while a != b:
    cycles.append(b)
    visited[b] = True
    b = parent[b]

# 사이클의 노드들은 이미 visited 되어있다.
# 사이클의 노드들을 기준으로 DFS 를 진행한다.
for node in cycles:
    parent[node] = node
    dfs(node, node)


# 같은 그룹에 존재한다면 1을 출력한다.
for i in range(M):
    u, v = map(int, input().split())
    if parent[u] == parent[v]:
        print(1)
    else:
        print(2)