dfs (6) 썸네일형 리스트형 백준 1937 - 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다음 dp 테이블을 세운다. dp[i][j] := 좌표 (i, j)에서 시작했을 때 가질 수 있는 최장 경로의 길이 각 좌표마다 가질 수 있는 최장 경로를 DFS로 검색하면 $O(V^{2}E)$가 되어 시간 초과를 받게 된다. 이를 $O(V^{2})$로 줄여보자. 각 정점마다 DFS를 수행하면서 거쳐간 정점에 저장한 지역 최장 경로는 일단 저장한다. 그리고 이미 거쳐간 정점에 대해서는 .. 백준 1325 - 효율적인 해킹 https://www.acmicpc.net/problem/1325 A가 B를 신뢰한다는 것은 B가 A를 해킹할 수 있다는 뜻이며 B -> A 방향의 엣지가 주어지는 것으로 이해할 수 있다. 이 문제는 노드가 최대 10000개이며 우리는 감각적으로 PS를 할 때 1초에 1억 번(최근엔 2~3억) 번의 연산을 할 수 있음을 알고 있다. 즉 모든 노드에 대해 일일이 DFS/BFS를 수행하면 노드 한 개가 자기 자신을 포함하여 최대 10000개의 노드를 탐색하므로 $10^{4} \times 10^{4} = 10^{8}$번의 연산을 해야 하고 이는 5초라는 주어진 시간에 걸맞은 풀이가 된다. 각 노드마다 BFS혹은 DFS를 이용하여 최대로 해킹 가능한 컴퓨터가 몇 대인지 세주면 된다. 이렇게 구한 값은 2차원 선.. [ICPC] 백준 20047 - 동전 옮기기 https://www.acmicpc.net/problem/20047 힌트 더보기 선택한 동전은 단 두 개다. 완전 탐색을 해도 분기가 많이 발생하지 않는다. 풀이 더보기 동전 두 개의 위치를 바꿔가면서(그들의 상대적인 순서는 유지하고) T와 같은 배치를 만들 수 있는지 묻는 문제다. 배치 S에서 주어진 index에 해당하는 동전을 따로 뺀 뒤 동전을 처음부터 배치한다고 하면 다음 분기로 배치를 결정할 수 있다. 동전 두 개를 제거한 S의 배치 순서를 pos라 하고 T의 순서를 idx라 한다면 1. S[pos]와 T[idx]가 일치하면 그대로 놓기 2. T[idx]와 동전 두 개 중 하나를 조건에 맞게 놓기 이를 DFS로 구현하면 정답을 받을 수 있다. 자세한 구현은 밑에 소스를 참조한다. #pragma .. Rerooting Technique on Tree 이 게시글에서는 트리에서 할 수 있는 rerooting technique라는 것을 다뤄본다. Rerooting? 자연수 N개의 노드로 구성되고 루트가 정해진 트리가 주어져 있고 배열에 다음과 같은 정보가 담기길 원한다고 해보자. sub[i] = i번째 노드가 루트인 서브 트리에 대해 해당 트리에 속한 노드의 개수 이 배열을 완성하기 위해서 어떻게 해야 할까? 먼저 생각나는 단순한 방법으로는 각 노드마다 dfs를 돌아 노드의 개수를 세는 $O(N^{2})$ 방법을 떠올릴 수 있다. 하지만 당연하게도 이런 글을 쓴다는 것은 $O(N^{2})$ 시간 복잡도로 해결할 수 없도록 N의 크기가 $10^{5}$ 이상인 경우에 대해 푸는 방법을 알아보는 것이므로 위 방법은 쓸 수 없다. 게다가 각 노드가 루트라고 할 .. 오일러 투어(Euler Tour) 기초 오일러 투어? 오일러 투어는 트리에서 백트래킹을 할 때 그 흔적을 남기는 순회로 볼 수 있다. 오일러 트리를 이용하면 DFS를 하면서 몇 번째 이동에 어떤 정점에 머무르는지, 어떤 부모 노드의 자식 중 가장 큰 번호가 무엇인지, 그리고 해당 정점이 어느 시점에 처음으로 방문되고 어느 시점에 마지막으로 방문되는지 파악할 수 있다. 오일러 투어로 무엇을 하려는지에 따라 그 구현이 달라지므로 위 경우들에 대한 구현을 소개한다. 1. x번째 이동에 도착한 정점 다음 코드는 DFS를 할 때 특정 시점에 방문한 노드를 기록한다. vector footprint; vector tree[100001]; bool discovered[100001]; void euler_tour(int node) { footprint.pus.. 이전 1 2 다음
