[백준 12383번] Diamond Inheritance (Large) (Python/파이썬)

https://www.acmicpc.net/problem/12383

12383번: Diamond Inheritance (Large)

구글 Code jam에 출제된 문제이다.

그래프의 한 노드에서 시작해서 다른 노드에 도착하는 경로의 가짓수가 최소 2가지 이상이면 Diamond Inheritance라고 한다.

클래스의 상속관계를 그래프로 표현한 것인데 A -> B라고 되있으면 B는 A의 부모 클래스 인것이다.

(즉, A는 B로부터 상속받은 자식 클래스다.)

 

상속관계를 표현한 그래프 문제이므로 그래프 탐색을 이용해서 BFS나 DFS를 이용하면 쉽게 문제를 해결할 수 있다.

필자는 BFS를 사용했다.

Diamond = False를 확인용 변수로 둬서, 경로가 2가지 이상이면 Diamond = True로 해줌으로써 문제를 해결하였다.

방문 리스트 visited를 만들어서 한번 방문했던 노드를 다시 방문하면 해당 노드로 향하는 경우의 수가 2가지 이상이라는 의미이다.

코드는 다음과 같다.

 

import sys
from collections import deque
input = sys.stdin.readline

def BFS(e):
  global Diamond
  queue = deque([])
  queue.append(e)
  while queue:
    tmp = queue.popleft()
    for i in inheritance[tmp]:
      if not visited[i]:
        visited[i] = True
        queue.append(i)
      else:
        Diamond = True
        return


T = int(input())
for tc in range(1,T+1):
  Diamond = False
  class_cnt = int(input())
  inheritance = [[] for _ in range(class_cnt+1)]
  for i in range(1,class_cnt+1):
    tmp = list(map(int,input().split()))
    num = tmp[0]
    if num != 0:
      for j in range(1,num+1):
        inheritance[i].append(tmp[j])

  for i in range(1,class_cnt):
    visited = [False for _ in range(class_cnt+1)]
    BFS(i)
    if Diamond:
      print('Case #{0}: Yes'.format(tc))
      break
  else:
    print('Case #{0}: No'.format(tc))

 

 

 

 

 

 

 

큰 어려움 없이 바로 해결했다.