[Python] 백준 - 1717 집합의 표현

 

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

 

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

 

 

문제해결방법 - 

 

1. 생각해봐야 하는 조건 

 

1) 트리는 순환계가 아니다. -> 순환이 생기면 트리가 아니다. 방문리스트로 판별할 수 있다.

2) 주어진 그래프에서 끊어진 트리들이 있을 수도 있다. -> 방문리스트로 구분할 수 있다.

 

2. dfs, bfs를 활용하여 구현할 수 있다. 

 

dfs의 경우, 각 재귀에서 False를 리턴하더라도, 방문리스트에 반영되는 것에 누락이 없다.

bfs의 경우, 재귀가 아니라 함수 내부의 while문에서 이루어지기 때문에, 순환일 경우 바로 return False를 하면 

다른 노드들이 방문리스트에 반영이 되지 않을 수 있다. 이럴 땐, bool 변수로 장치를 하나 만들어 주면 된다.

 

 

- dfs 알고리즘 활용

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

def dfs(idx, pre):
	v[idx] = 1
	for next in graph[idx]:
		if next == pre:
			continue
		if v[next] == 1:
			return False
		if v[next] == -1:
			t = dfs(next, idx)
			if not t:
				return False
	return True

case = 0
while True:
	try:
		n, m = map(int, input().split())
		if n == 0 and m == 0:
			break
		case += 1
		cnt = 0
		graph = [[] for _ in range(n+1)]
		v = [-1 for _ in range(n+1)]
		for _ in range(m):
			a, b = map(int, input().split())
			graph[a].append(b)
			graph[b].append(a)
		for i in range(1, n+1):
			if v[i] == -1:
				if dfs(i, 0):
					cnt += 1
		if cnt == 0:
			print(f"Case {case}: No trees.")
		elif cnt == 1:
			print(f"Case {case}: There is one tree.")
		else:
			print(f"Case {case}: A forest of {cnt} trees.")
	except:
		break

 

- bfs 알고리즘 활용

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

def bfs(idx):
	chk = True
	q = deque()
	q.append(idx)
	while q:
		idx = q.popleft()
		if v[idx] == 1:
			chk = False
		v[idx] = 1
		for next in graph[idx]:
			if v[next] == -1:
				q.append(next)
	return chk

case = 0
while True:
	try:
		n, m = map(int, input().split())
		if n == 0 and m == 0:
			break
		case += 1
		cnt = 0
		graph = [[] for _ in range(n+1)]
		v = [-1 for _ in range(n+1)]
		for _ in range(m):
			a, b = map(int, input().split())
			graph[a].append(b)
			graph[b].append(a)
		for i in range(1, n+1):
			if v[i] == -1:
				if bfs(i):
					cnt += 1
		if cnt == 0:
			print(f"Case {case}: No trees.")
		elif cnt == 1:
			print(f"Case {case}: There is one tree.")
		else:
			print(f"Case {case}: A forest of {cnt} trees.")
	except:
		break