-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
DFS 문제 하나 여쭤봅니다!..
24.02.25 14:45 작성 조회수 99
1
강의를 들어보다가 백준 - 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)
답변을 작성해보세요.
1
개발자로 취직하기
지식공유자2024.02.25
안녕하세요! 해당 문제는 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)
답변 1