글 읽기 - 파이썬) 예제도 다 맞는데 20%에서 계속 틀려요.

hashin0602 2년 전 0

트리에 속하지 않는 노드는 바로 한개의 트리로 생각해서 cnt_tree에 더해줬고 그다음부터는 간선으로 연결되어있는

노드에서 트리가 몇개있는지 알기 위해서 함수로 돌려서 확인해보았는데 20%에서 계속 틀립니다.. 이유좀 알려주세요

import sys
from collections import deque

def tree_search(tree):
    q=deque()
    arr=[]
    cnt=0
    sum=0
    q.append(tree[0])
    arr.append(tree[0])
    visit[q[0]]=1
    while q:
        front=q.popleft()
        for j in graph[front]:
            if visit[j]==0:
                visit[j]=1
                q.append(j)
                arr.append(j)  
    if arr == tree: #만들어질 트리가 하나
        for i in arr:
            sum+=len(graph[i]) #간선의 개수
        if len(arr)-1 == sum/2: #트리의 조건
            cnt+=1
            tree.clear()
            return cnt,tree
        else:
            tree.clear()
            return cnt,tree
    else: # 만들어질 트리가 여러개
        for i in arr:
            sum+=len(graph[i])
        if len(arr)-1 == sum/2:
            cnt+=1
            tree=[x for x in tree if x not in arr] #다음 트리를 찾기
            return cnt,tree
        else:
            tree=[x for x in tree if x not in arr]
            return cnt,tree

case=0
while True:
    n,m=map(int,sys.stdin.readline().split())
    if n==0 and m==0:
        exit()
    graph=[[] for _ in range(n+1)]
    visit=[0 for i in range(n+1)]
    case+=1 
    cnt_tree=0
    tree=[]
    for i in range(1,m+1):
        a,b=map(int,sys.stdin.readline().split())
        if not a in tree:
            tree.append(a)
        if not b in tree:  
            tree.append(b)
        graph[a].append(b)
        graph[b].append(a)
    if n == m:
        print('Case %d: No trees.' %case)
    else:
        cnt_tree += n-len(tree) #트리에 속하지 않는 노드는 더해주기
        while tree:
            cnt,tree=tree_search(tree) # 간선으로 연결되어있는것들중에 트리가 만들어지면 더해주기
            cnt_tree+=cnt
    
    if cnt_tree==1:
        print('Case %d: There is one tree.' %case)
    elif cnt_tree > 1:
        print('Case %d: A forest of %d trees.'%(case,cnt_tree))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬) 예제도 다 맞는데 20%에서 계속 틀려요.

hashin0602 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말