[백준] 4803번 : 트리

4803번: 트리

4803번: 트리

🤔 문제분석

특정 노드로 부터 시작하여 사이클이 존재하는지 확인하면 된다. 방문 체크 배열을 두어 사이클이 발생했었던 노드는 다시 방문하지 않는다. 사이클이 발생하는 유무는 너비우선탐색으로 찾아내었는데, 입력받은 간선을 계속 따라가 가면서 방문했던 노드를 또다시 방문했다면 사이클이 발생한 것이다.

💻 코드

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

def findCycle(start):
    isCycle = False
    q = deque()
    q.append(start)
    
    while q:
        cnt_node = q.popleft()
        if visited[cnt_node]:
            isCycle = True
        
        visited[cnt_node] = 1
        
        for adj_node in graph[cnt_node]:
            if visited[adj_node] == 0:
                q.append(adj_node)
                
    return isCycle

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

while n != 0 or m != 0:
    graph = [[] for _ in range(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)
    

    for node in range(1, n+1):
        if visited[node] == 0:
            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())

🎯 피드백 및 개선사항

사이클이 발생하는 조건만 해결하면 문제를 쉽게 해결할 수 있었습니다.