백준 4803 트리 파이썬 풀이

난이도 : 골드4

풀이일 : 2403085

https://www.acmicpc.net/problem/4803

4803번: 트리

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

문제 이해

 

처음에 도대체 왜 테스트케이스 1의 트리가 세 개 인가 이해가 안갔는데, 써보고 나이 이해했다.

아무 노드와도 연결되어 있지 않은 노드는 그 자체로 트리 한 개가 된다는 것을 이해한 후 풀이를 시작했다.

---

풀이 코드

import sys
from collections import deque

# 사이클 여부 확인
def iscylcle(num):
    queue = deque([num])
    visited = [False] * (n + 1)
    while queue:
        # x 방문 전적이 있다면 사이클
        x = queue.popleft()
        if visited[x]:
            return 0
        visited[x] = True
        # x와 연결된 노드 검사
        for nx in tree[x]:
            # 검사 여부
            check[nx] = False
            # 방문하지 않았던 연결 노트 queue 추가
            if not visited[nx]:
                queue.append(nx)
    return 1

# 테스트 케이스
tc = 0
while True:
    n, m = list(map(int, sys.stdin.readline().split()))
    tc += 1
    # 입력이 0 0 일 경우 종료
    if n == 0:
        break
    # 사이클 검사 수행 여부
    check = [True] * (n + 1)
    # 연결 정보
    tree = [[] for _ in range(n + 1)]
    # 트리 수
    count = 0

    # 입력
    for _ in range(m):
        s, e = list(map(int, sys.stdin.readline().split()))
        if s > e:
            s, e = e, s
        tree[s].append(e)
        tree[e].append(s)

    # 사이클 검사 미수행 노드에 대해 함수 실행
    for i in range(1, n + 1):
        if check[i]:
            if iscylcle(i):
                count += 1

    # 출력
    if not count:
        print(f'Case {tc}: No trees.')
    elif count == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {count} trees.')

• tc : 테스트케이스 번호 출력을 위한 변수
• n, m 이 0, 0으로 주어질 때까지 입력 받기 -> 둘 중 어느 것도 0이 될 수 없으니 n으로맘 종료 조건 설정
• check : 해당 인덱스의 노드에 대해 사이클 여부 검사를 수행했는지 기록하는 boolean 배열
• tree : 각 노드와 연결된 노드 정보를 저장할 이차원 배열
• count : tree의 개수
• 입력 : 방향 정보가 없으니 s, e 양방향 연결 노드 기록
• 사이클 검사 수행 : 이전에 사이클 검사가 이루어지지 않았던 노드에 대해 iscycle 함수 실행
• iscycle : bfs 방식 사이클 검사
  • queue에서 popleft 한 요소를 이미 방문한 적이 있다면 사이클이므로 return
  • queue에서 popleft 한 요소와 연결된 요소들을 방문한 적이 없다면 queue에 추가
• 출력 

---

느낀점

• 쉬운 문젠데 해결을 못해서 한참 걸렸다. 원래는 queue에 추가할 때 해당 노드를 검사했는데, 이렇게 저렇게 해봐도 내내 틀리다가 queue에서 뽑아 방문할 때 방문 여부를 추가했더니 해결되었다.
• 익숙해지면 파이썬 자바 한 문제씩 풀어야지 곧