정점(vertex)들의 차수(degree) 목록이 주어졌을 때, 이 차수들이 트리(tree)를 나타내는지 아니면 일반적인 그래프(graph)를 나타내는지 판별해야 합니다.
예를 들어 deg = [2,2,3,1,1,1]이 입력으로 주어지면 결과는 Tree입니다.
해결 원리
이 문제는 그래프 이론의 두 가지 기본 성질을 활용하면 간단하게 해결할 수 있습니다.
- 트리의 성질: n개의 정점을 가진 트리는 정확히 n−1개의 간선을 가집니다.
- 핸드셰이킹 보조정리(Handshaking Lemma): 그래프에서 모든 정점 차수의 합은 간선 개수의 2배와 같습니다.
따라서 주어진 차수들의 합이 2 × (정점 개수 − 1)과 일치한다면 해당 정점들은 트리를 형성하고, 그렇지 않다면 일반 그래프로 판단합니다.
알고리즘 단계
- vert ← 정점의 개수
- deg_sum ← 모든 차수 값의 합
- 만약 2 × (vert − 1) == deg_sum이면 'Tree'를 반환
- 그 외의 경우에는 'Graph'를 반환
참고로, 간선 개수가 n−1개라는 조건만으로는 그래프의 연결 여부까지 완전히 보장되지 않습니다. 따라서 엄밀한 트리 판별이 필요하다면 연결성 검사를 함께 수행하는 것이 좋지만, 본 문제에서는 위 조건만으로 판별합니다.
예제 코드
def solve(deg):
vert = len(deg)
deg_sum = sum(deg)
if 2*(vert-1) == deg_sum:
return 'Tree'
return 'Graph'
deg = [2,2,3,1,1,1]
print(solve(deg))
입력
[2,2,3,1,1,1]
출력
Tree