글 읽기 - 파이썬 촌수 계산 반례가 있을지 확인 부탁드립니다.

dusrlf13 3년 전 0

리스트를 이용해서 항렬을 저장했고 리스트의 인덱스가 부모, 인덱스에 저장된 수가 자식의 인덱스로 표현했습니다. 0번 인덱스는 사용하지 않았구요.

재귀를 이용해서 풀이를 시도해봤는데, 직접 반례를 만들어 해봐도 어느 부분에서 틀렸는지 잘 모르겠습니다...도움 주시면 감사하겠습니다 ㅠㅠ

참고 알고리즘에 그래프 탐색으로 푸는 문제로 되어있는데, 어떻게 풀이를 해야 그래프 탐색을 이용하는 방향으로 푸는건지도 조언 부탁드립니다...

해당 코드를 제출해보면 18% 정도에서 틀렸습니다를 받았습니다.

# 촌수계산 https://www.acmicpc.net/problem/2644

n = int(input())

p1, p2 = map(int, input().split())

m = int(input())

graph = [[] for _ in range(101)]
count = 0

for _ in range(m):
    # x는 y의 부모
    x, y = map(int, input().split())
    graph[x].append(y)

# p1의 부모 알아내기
def findP1(p1):
    global count
    index = 0
    for i in range(1, 101):
        if p1 in graph[i]:
            count+=1
            index = i
            return index
        else:
            continue
    # 부모가 없는 최종 노드라면 자기자신을 반환
    index = p1
    return index

# p2의 부모 알아내기
def findP2(p2):
    global count
    index = 0
    for i in range(1, 101):
        if p2 in graph[i]:
            count+=1
            index = i
            return index
        else:
            continue
    # 부모가 없는 최종 노드라면 자기자신을 반환
    index = p2
    return index

def Search(p1, p2):
    global count
    last1 = False
    last2 = False

    P1 = findP1(p1)
    P2 = findP2(p2)

    # 두 노드의 부모가 동일하다면 출력 후 종료
    if P1 == P2:
        print(count)
        return
    
    for i in range(1, 101):
        if P1 in graph[P2]:
            print(count+1)
            return
        elif P2 in graph[P1]:
            print(count+1)
            return

    # 최종 노드인지 검사
    for i in range(1, 101):
        if P1 not in graph[i]:
            last1 = True
        else:
            break
    for i in range(1, 101):
        if P2 not in graph[i]:
            last2 = True
        else:
            break

    # 연관 없는 최종 노드뿐이라면 촌수 관계 없음
    if last1 == True and last2 == True:
        print(-1)
        return

    Search(P1, P2)

Search(p1, p2)

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

문제

문제

출처

ICPC

파이썬 촌수 계산 반례가 있을지 확인 부탁드립니다.

dusrlf13 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말