dfs 썸네일형 리스트형 BOJ 16964 - DFS 스페셜 저지 (G3) 사용 알고리즘 DFS 풀이 주어진 방문 순서가 DFS의 성질을 만족한다면 DFS라고 볼 수 있을 것이다. 트리에서 DFS의 성질 중 하나는, 어떤 정점을 루트로 하는 서브트리는 그 서브트리상의 모든 정점을 DFS로 방문한다는 것이다. 또한 이 성질은 모든 정점에서 성립하므로, 각 정점에서 이 성질이 성립하는지만 확인하는 것으로 충분하다. 이를 간단하게 확인하는 방법은, 서브트리의 정점 개수와 주어진 순서대로 방문했을 때의 서브트리의 정점 개수가 같은지를 확인하면 된다. 이 방법이 왜 가능한지를 생각해보자. 방문 순서가 올바른 DFS가 아니라면 방문 순서가 잘못된 지점이 있을 것이다. 그 지점에서는, DFS를 리프 노드까지 진행하지 않고 중간에 다른 곳으로 이동했을 것이다. 위 그림에서 잘못된 순서인 빨간.. 더보기 BOJ 18770 - 불안정한 물질 (P2) #dfs #tree-dp 구현이 짜증나는 문제다. 문제는 꽤 재밌는데, n개의 노드와 n개의 간선이 있다. 이상태에서 인접하지 않은 정점만 골라서 최대 점수를 얻는 문제다. 만약 n개의 노드가 다 연결되어 있다면 그 그래프는 트리에 하나의 간선을 추가한 형태일 것이고, 그 간선에 의해 indegree가 2인 정점이 생긴다. 그래서 이 정점과 그 부모를 골라내서 이 정점들끼리는 미리 고를지 말지를 결정해두고, 간선을 하나 지우면 트리가 된다. 그 이후로 트리 dp를 돌리면 된다. 과연 이게 가능할까? 생각해보면 트리에서 간선만 하나 추가한 형태이기 때문에, 고려할 정점은 무조건 3개이다. 그래서 이 3개끼리 잘 케이스를 나눠가면서 연결그래프를 유지하되 간선을 하나 지울 수 있다. 그러면 트리가 되므로 .. 더보기 이전 1 다음
