[백준 17834번] 사자와 토끼 (Python3)

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

def DFS(now,sign):
  global gameover
  if gameover:
    return
  visited[now] = sign
  for next in graph[now]:
    if visited[next]==sign:
      gameover = 1
    if not visited[next]:
      DFS(next,-sign)

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

graph = [[] for i in range(N+1)]
for _ in range(M):
  x,y = map(int,input().split())
  graph[x].append(y); graph[y].append(x)

visited = [0]*(N+1)
gameover = 0
DFS(1,1)
print(0 if gameover else visited.count(-1)*visited.count(1)*2)

간단한 DFS 문제

풀이는 금방 생각났는데 이상한 곳에서 헤맸던 문제였다.

 

그래프에서 홀수번째 노드와 짝수번째 노드를 구분할 수 있는지에 대한 문제이다. 홀수번째 노드와 짝수번째 노드가 구분되면, 각각 홀수, 짝수번 노드에 사자와 토끼가 위치하는 경우 영원히 둘은 만날 수 없게된다. 이를 이용하는 문제이다.

 

풀이를 설명하면,

1. DFS로 탐색한다.

2. 현재 부호가 1이면 visited에 1로 기록하고, -1이면 -1로 기록한다.

3. 현재 부호가 1인데 다음 노드가 이미 방문된 상태고, 부호가 현재 부호와 같다면, 홀수 짝수 노드를 구분할 수 없으므로 0을 출력한다.

4. 3에 해당하지 않는 경우 1로 기록된 노드의 수 * -1로 기록된 노드의 수 * 2를 출력한다 (2를 곱하는 이유는 사자가 홀수노드일 때와 토끼가 홀수 노드일 때 두가지가 있으므로)

 

헤맸던 이유는 홀수 노드의 수와 짝수 노드의 수가 당연히 각각 N/2 또는 N/2+1이라고 착각했었다. 그런데 다시 생각해보니 그렇지 않다는 것을 알게 되었다.

 

 

오늘의 교훈) 홀수 노드와 짝수 노드의 수는 정확히 절반이 아니다