글 읽기 - 파이썬 코드 반례 찾아주실 수 있나요??

cksgh1735 1년 전 0

78%에서 fail이 뜹니다.. 어떤 반례가 있을까요??

또 코드에서 어떤 부분을 개선하면 좋을지 조언 부탁드리겠습니다

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

N = int(input())
parent_info = list(map(int, input().split()))
Removed = int(input())

# 각 부모당 자식의 정보들 -> 자식의 개수가 0인 node가 leaf node
tree = [[] for _ in range(N)]
# 생존 여부
alive = [True for _ in range(N)]


for i in range(N):
    if parent_info[i] != -1:
        tree[parent_info[i]].append(i)  # 자식 추가


def BFS(p):
    queue = deque([p])
    # 방문 여부
    visited = [False for _ in range(N)]
    visited[p] = True
    alive[p] = False

    while queue:
        p = queue.popleft()

        for c in tree[p]:
            if not visited[c]:
                queue.append(c)
                visited[c] = True
                alive[c] = False


def solve(removed_node):
    cnt = 0
    alive[removed_node] = False
    for child in tree[removed_node]:
        BFS(child)

    for i in range(N):
        if alive[i] and len(tree[i]) == 0:
            cnt += 1
    return cnt


print(solve(Removed))

cinador 1년 전 2

반례드립니다.

3
-1 0 1
2
    
# Output
0
    
# Answer
1

cksgh1735 1년 전 0

선생님 답변 감사합니다. 올려주신 반례를 보고 아래와 같이 코드를 수정했는데 이번에는 100%까지 채점이 완료되다가 런타임에러가 납니다.. ㅠ

어디가 잘못된건가요??

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

N = int(input())
parent_info = list(map(int, input().split()))
Removed = int(input())

# 각 부모당 자식의 정보들 -> 자식의 개수가 0인 node가 leaf node
tree = [[] for _ in range(N)]
# 생존 여부
alive = [True for _ in range(N)]


for i in range(N):
    if parent_info[i] != -1:
        tree[parent_info[i]].append(i)  # 자식 추가


def BFS(p):
    queue = deque([p])
    # 방문 여부
    visited = [False for _ in range(N)]
    visited[p] = True
    alive[p] = False

    while queue:
        p = queue.popleft()

        for c in tree[p]:
            if not visited[c]:
                queue.append(c)
                visited[c] = True
                alive[c] = False
                # # 부모의 리스트에서 해당 자식 제거
                # tree[p].remove(c)


def solve(removed_node):
    cnt = 0
    alive[removed_node] = False

    # 리프노드를 삭제하는 경우
    if len(tree[removed_node]) == 0:
        # 삭제하려는 노드의 부모 인덱스 구하기
        parent_index = 0
        for i, parent in enumerate(tree):
            for child in parent:
                if child == removed_node:
                    parent_index = i
        # 삭제하려는 노드을 부모에서 제거
        tree[parent_index].remove(removed_node)
    # internal 노드를 삭제하는 경우
    else:
        for child in tree[removed_node]:
            BFS(child)

    for i in range(N):
        if alive[i] and len(tree[i]) == 0:
            cnt += 1
    return cnt


print(solve(Removed))

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

문제

문제

출처

ICPC

파이썬 코드 반례 찾아주실 수 있나요??

cksgh1735 1년 전 0

cinador 1년 전 2

cksgh1735 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말