[Python] 백준 - 4803 트리

백준 - 4803 트리

 

문제

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

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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

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

def dfs(idx, pre):
    global nnt, ent
    v[idx] = 1
    nnt += 1
    for next in graph[idx]:
        ent += 1
        if next == pre:
            continue
        if v[next] == 0:
            dfs(next, idx)

case = 0
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    graph = [[] for _ in range(n+1)]
    v = [0 for _ in range(n+1)]
    case += 1
    cnt = 0
    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] == 0:
            nnt, ent = 0, 0
            dfs(i, 0)
            ent //= 2
            if nnt-1 == ent:
                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.")

 

- 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

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

def bfs(idx):
    q = deque()
    q.append(idx)
    v[idx] = 1
    nnt, ent = 0, 0
    while q:
        idx = q.popleft()
        nnt += 1
        for next in graph[idx]:
            ent += 1
            if v[next] == 0:
                v[next] = 1
                q.append(next)
    ent //= 2        # 간선은 양방향이니 2로 나눠준다.
    if nnt-1 == ent: # 트리는 정점-1 == 간선이다.
        return True
    else:
        return False

case = 0
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    graph = [[] for _ in range(n+1)]
    v = [0 for _ in range(n+1)]
    case += 1
    cnt = 0
    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] == 0:
            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.')
    elif cnt > 1:
        print(f'Case {case}: A forest of {cnt} trees.')