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

Question

강의를 들어보다가 백준 - 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)

개발자로 취직하기 · Answer

안녕하세요! 해당 문제는 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)