글 읽기 - DFS,파이썬 이유를 잘모르겠습니다 ㅠㅠ

didwns7347 3년 전 0

인덱스 번호 기준으로 이전에 일어난 사건을 저장하는 before과

이후에 일어난 사건을 저장하는 after 리스트를 생성하고 입력 받으면서 값을 저장한후

테스트 케이스에서 a,b 이주어지면 DFS를 이용해 a에서 시작되는 after리스트와 bfore 리스트를 탐색해

bfore리스트에서 b를 탐색하면 1을 출력하고 after리스트에서 b를 탐색하면 -1을 둘다 에서탐색하지 못하면

0을 출력하는 방식으로 구해봤습니다. 하지만 틀.렸.습.니.다.

생각이 잘못된 건가요??

n,k = map(int,input().split())
before=[ [] for x in range(n+1)]
after=[ [] for x in range(n+1)]
answer=[]
for x in range(k):
    a,b=map(int,input().split())
    before[b].append(a)
    after[a].append(b)

def BeforeDFS(a,b):
    Bcheck[a]=True
    if a==b:
        answer.append(1)
        return True
    for x in before[a]:
        if Bcheck[x]==False:
            return BeforeDFS(x,b)
    return False

def AfterDFS(a,b):
    Acheck[a]=True
    if a==b:
        answer.append(-1)
        return True
    for x in after[a]:
        if Acheck[x]==False:
            return AfterDFS(x,b)
    return False

t=int(input())

for x in range(t):
    Acheck=[False for x in range(n+1)]
    Bcheck=[False for x in range(n+1)]
    a,b=map(int,input().split())
    if not AfterDFS(a,b) and  not BeforeDFS(a,b):
        answer.append(0)

for x in answer:
    print(x)

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

문제

문제

출처

ICPC

DFS,파이썬 이유를 잘모르겠습니다 ㅠㅠ

didwns7347 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말