[BOJ][Python] 백준 17834 번: 사자와 토끼

1일 1PS 74일차!

📚 문제

---

[골드 1] - 사자와 토끼

💡 풀이 과정

---

• 실제 예제 그래프를 그려봤을 때 사자와 토끼가 만나는 경우는 홀수개의 노드로 이루어진 사이클이 존재할 때이다.
• 그래프 전체에 대해서 홀수개의 노드로 이루어진 사이클이 하나라도 있다면 토끼와 사자는 결국 만나게 된다.
• 그렇다면 사이클을 우선 파악하고 경우의 수를 파악해보자.
  • 사이클은 DFS 를 사용해서 파악한다.
  • 1번부터 DFS 를 사용해 지나가는 모든 노드를 배열로 추가한다.
  • 만약 다음 노드가 이미 배열에 존재한다면 arry[nodeIndex:] 를 통해 사이클을 얻어낼 수 있다.
  • 또한 사이클을 정렬해서 중복된 사이클은 포함되지 않도록 한다.
• 이를 통해 얻어낸 사이클들 중 길이가 홀수인 경우가 있으면 print(0) 을 한다.

• 이제 사자와 토끼가 만나지 않는 경우의 수가 반드시 존재하는 경우들에 대해서 경우의 수를 계산해야한다.
• 우선 사자와 토끼가 인접한 경우는 항상 만날 수 없다.
  • 즉 그래프 전체의 원소의 개수가 해당 경우의 수이다.
• 이제 사자와 토끼의 거리가 3, 5, 7 … 인 경우에 대해서 파악해야한다.
  • 이를 위해 5만번의 BFS 는 당연히 말이 안된다.

...

# find all cycle
cycles = []
def dfs(now, prev, cycle):
    for node in graph[now]:
        # 되돌아가는 것 방지
        if node == prev:
            continue

        # 사이클 판별 시
        if node in cycle:
            index = cycle.index(node)
            cycle_list = cycle[index:]
            cycle_list.sort()
            if cycle_list not in cycles:
                cycles.append(cycle_list)
        else:
            cycle.append(node)
            dfs(node, now, cycle)
            cycle.remove(node)
            if not cycle:
                cycle = []

...

dfs(1, -1, [1])

# 홀수 개의 사이클이 있는 지 확인
flag = True
for cycle in cycles:
    if len(cycle) % 2 == 1:
        flag = False
        break

if flag:
    ...
else:
    print(0)

• 이를 다시 생각해보면 결국 수풀을 2가지로 구분지을 수 있다.
  • 1번 수풀에 대해서 거리가 1, 3, 5 .. 홀수 거리인 수풀들은 무조건 만나지 않는다.
  • 1번 수풀에 대해서 거리가 0, 2, 4 … 짝수 거리인 수풀들은 무조건 만난다.
  • 즉, 1번 수풀에 대해서 홀수 수풀, 짝수 수풀에서 하나씩 추출한다면 두 수풀은 절대 만나지 않는다.

• 이를 DFS 에 다시 적용시켜보면 굳이 사이클을 찾아낼 필요가 없다.
  • visited 에 존재하는 거리와 새로 계산한 거리의 홀짝 여부가 다르면 홀수 거리의 사이클이므로 중단하고 0을 출력한다.
• 이를 위해 현재 노드와 거리를 이용한 DFS 를 실행한다.
  • visited 에 거리를 저장하고 visited 노드에 다시 방문한다면 해당 거리와 지금 계산한 노드의 홀짝이 동일한 지 검사한다.
  • 새로운 노드를 추가할 때는 홀짝 카운팅을 추가한다.
• 이후 홀수 수풀 * 짝수 수풀 * 2 가 정답이다.

📌포인트

---

• DFS
  • DFS 에서 배열을 deepcopy 해 넘기지 않아도 되는 이유는 이전에 설명했다.
  • DFS 는 끝까지 모든 경우를 탐색하고 되돌아오기 때문에 리소스에 대해서 사용하고 다시 복원시켜놓는다면 리소스가 겹쳐 오류가 발생할 수 없다.
  • 같은 이유로 DFS 시 사이클이 없다면 이전 노드를 함께 넘겨주면 visited 를 사용하지 않아도 된다.

💻 코드

---

import sys
from collections import deque

input = sys.stdin.readline

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

graph = {}

for _ in range(M):
    u, v = map(int, input().split())

    # 그래프 추가
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []

    graph[u].append(v)
    graph[v].append(u)


# 수풀 그룹핑 및 검사
def bfs():
    # 짝수 수풀과 홀수 수풀. 1번 노드 미리 입력
    cnt = [1, 0]
    queue = deque()
    visited = [0] * (N + 1)
    visited[1] = 1
    queue.append((1, 1))

    while queue:
        n, c = queue.popleft()

        for node in graph[n]:
            # 만약 visited 노드라면
            if visited[node] != 0:
                # 이전에 계산한 홀짝과 지금 계산한 홀짝이 동일한 지 파악
                if visited[node] % 2 == c % 2:
                    # visited[node] 와 c + 1 이 동일해야한다. c 와 동일한 것은 다르다는 뜻.
                    # 만약 홀짝이 다르다면 사자와 토끼는 무조건 만나므로 바로 0 을 출력
                    return False
                continue

            # visited 기록
            visited[node] = c + 1

            # 홀짝 수풀 개수 카운팅
            cnt[c % 2] += 1

            queue.append((node, c + 1))

    return cnt


counts = bfs()
if counts:
    print(counts[0] * counts[1] * 2)
else:
    print(0)