백준 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 

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

 

예제 출력 1

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

 

 

 

 

---

DFS

 

 

사실 어떻게 접근해야할지 잘 모르겠어서 검색해봄.
검색하니 트리 or 그래프 문제의 대부분은

BFS 혹은 DFS 로 풀더라.

 

 

시간 효율을 중시 여겨서 더 효율이 좋은

DFS로 선택해서 공부해보기로 결정.

 

 

 

 

1. DFS 풀이에서는 리스트를 두 개 활용한다. 하나는 visited 리스트, 하나는 parent 리스트이다. visited[n]은 1이면 기방문, 0이면 미방문을 의미한다.
2. parent[n] = v 는 n의 부모 노드가 v임을 의미한다.

 

1. 1부터 n까지 visited가 0인 노드에 한해 DFS를 각각 돌려준다.DFS 로직을 살펴보면, 현 노드에 대해 인접 노드를 순회하면서 parent와 visited를 갱신하고 재귀를 호출한다.그리고 부모 노드가 아니면서 visited가 1인 경우가 핵심인데, 이는 곧 사이클임을 의미한다.만약 이 경우도 아니라면, 인접 노드의 parent와 visited를 갱신하고 재귀를 호출해준다. 인접 노드를 루트 노드로 하는 서브트리에 사이클이 존재하면, 즉 재귀 함수의 리턴값이 True이면 전체 트리 또한 사이클이 존재하는 그래프가 된다.
2. DFS를 부모-자식 방향으로 순회하고 있는데, 트리에서 자식 노드에서 그 인접 노드로 방문하고자할 때, visited가 1인 경우는 부모 노드인 경우밖에 없다. 즉, 이는 곧 사이클임을 의미하는 것이다.
3. 단, 이를 수행하기 전에 먼저 if로 검사할 것이 있는데, 우선 인접 노드가 자신의 부모 노드와 같은 경우는 이미 방문한 노드이므로 continue 해준다.
4. 이 DFS는 start 노드가 포함된 연결 그래프(연결 요소)를 모두 순회하면서 사이클이 있는지를 판단한다.

 

import sys
input = sys.stdin.readline

def findCycle(start):
    for adj_node in graph[start]:
        # 인접 노드가 자신의 부모 노드인 경우 패스
        if parent[start] == adj_node:
            continue
        
        # 인접 노드가 부모 노드가 아닌데 방문 이력이
        # 있다는 것은 곧 사이클을 의미함
        if visited[adj_node]:
            return True
        
        parent[adj_node] = start
        visited[adj_node] = 1
        # 인접 노드를 루트 노드로 하는 서브트리에
        # 사이클이 존재하면 곧 전체 트리에 사이클이
        # 존재하는 것과 같음
        if findCycle(adj_node):
            return True
    
    return False

n, m = map(int, input().split())
case = 1

while n != 0 or m != 0:
    graph = [[] for _ in range(n+1)]
    parent = [-1]*(n+1)
    visited = [0]*(n+1)
    count = 0
    
    # 양방향 매핑
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    # visited가 0인 모든 노드를 돌면서
    # 가능한 모든 연결 요소(연결 그래프)를 순회함
    for node in range(1, n+1):
        if visited[node] == 0:
            parent[node] = node
            visited[node] = 1
            if not findCycle(node):
                count += 1
    
    if count == 0:
        print(f'Case {case}: No trees.')
    elif count == 1:
        print(f'Case {case}: There is one tree.')
    else:
        print(f'Case {case}: A forest of {count} trees.')
    
    case += 1
    n, m = map(int, input().split())