DFS 문제 하나 여쭤봅니다!..

[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편

트리의 부모 찾기 (백준 11725)

해결된 질문

작성

198

강의를 들어보다가 백준 - 16964번 DFS 스페셜 저지 문제를 풀어 보았는데 여러개의 답이 나올 수 있는 경우를 특정하기가 어려줘 질문 남겨봅니다!..

graph에서 순차적으로 나오는 경우는 답을 구할 수 있는데 그래프에서 랜덤한 방향으로 진행될 시 어떻게 해야되는지 궁금합니다!..
제가 짜본 기본 코드입니다..ㅜㅜ 도움 부탁드립니다!

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 함수
def dfs(idx):
    global visited, answer, graph, order

    visited[idx] = True
    answer[idx] = order
    order += 1

    for i in graph[idx]:
        if not visited[i]:
            dfs(i)


# 0. 입력 조건 
N = int(input())
visited = [False] * (N+1)
answer = [0] * (N+1)
order = 1
graph = [[] for _ in range(N+1)]

# 1. 그래프 받아오기
for _ in range(N-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 2. dfs 수행
dfs(1)

# 3. 출력하기 
given = list(map(int, input().split()))
# answer.sort()
answer = answer[1:]
if given == answer:
    print(1)
else:
    print(0)

python 코딩-테스트 알고리즘 dfs python3

답변 1

개발자로 취직하기

지식공유자

안녕하세요! 해당 문제는 DFS를 정확히 이해해야 되기도 했지만, 한 노드를 기준으로 갈 수 있는 자식 노드들을 순서와 관계없이 구분할 방법도 필요했습니다. 그래서 무조건 정답이 뭔지를 찾거나, 작성하신 대로 모든 경우의 수를 다 따지면 시간 초과가 발생할 것 같아요!

그래서 필요한 것은 각 노드를 루트로 하는 서브트리의 크기를 게산하고, 각 노드의 높이(레벨)를 계산해야 됐습니다. 그래서 문제에서 주어진 정답이 순서와 관계 없이 정답이 될 수 있는지 서브트리 수준에서 판단이 필요했던 것으로 보입니다!

샘플 정답은 이걸 참고하시면 될 것 같습니다!

import sys
N = int(sys.stdin.readline())
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
ans= list(map(int,sys.stdin.readline().split()))
level=[False]*(N+1)
tsize = [0]*(N+1)
visited = [False]*(N+1)

def dfs(x,lv):
    if visited[x]:
        return 0
    visited[x]=True
    size=1
    level[x]=lv
    for i in range(len(graph[x])):
        next =graph[x][i]
        size+=dfs(next,lv+1)
    tsize[x]=size
    return size


if ans[0]!=1:
    print("0")
    sys.exit(0)
else:
    dfs(1,0)
    for i in range(1,N):
        x=ans[i]
        if tsize[x] == 1 or i + tsize[x] >=N:
            continue
        next = ans[i+tsize[x]]
        if level[next]>level[x]:
            print(0)
            sys.exit(0)
    print(1)

tlminn01

질문자

답변 너무 감사합니다!

덕분에 더 열심히 할 수 있습니다!!

인프런 커뮤니티 질문&답변

DFS 문제 하나 여쭤봅니다!..