dfs4 ETT 오일러 경로 테크닉, 근데 이제 펜윅을 곁들인 Euler Tour Technique 오일러 경로 테크닉 트리의 한 간선을 양방향 간선(or 반대 방향의 간선 두 개)로 생각한 뒤 루트에서 출발해 루트로 도착하는 그래프(트리)의 오일러 사이클을 찾는 것으로 트리를 표현하는 방식이다. * 오일러 사이클은 시작점=종점인 한붓그리기로 이해하면 됨 이렇게 144125566788997233 255667889972144133 255799887662331441 등... 트리가 주어지고 다음과 같은 쿼리가 주어진다고 하자. 1. i번 노드의 모든 하위 노드(자식, 자식의 자식...)의 값을 w만큼 증가한다. or i번 노드의 모든 상위 노드(부모, 부모의 부모...)의 값을 w만큼 증가한다. 2. i번 노드의 값을 출력한다. DFS로도 가능이야 하지만 트리의 깊이가.. 2021. 8. 5. BOJ7812 중앙 트리 7812번 중앙트리 트리와 각 간선의 가중치가 주어질 때 한 꼭짓점에 대해 모든 꼭짓점과의 거리 합이 최소일 때의 그 값을 구한다. 즉 중앙 정점과 모든 꼭짓점과의 거리 합을 구한다. DFS, DP 당연히 모든 점에 대해 거리를 다 계산해볼 순 없고 트리이므로 DFS, 중앙 정점이 될 수 있는 점을 DP로 찾아가며 푼다. 처음에 DFS 두 번에 푸는 방법으로 해결했는데, 한 번만으로도 충분했다. 일단 간선은 벡터 E에 간선을 { 자식 노드 , 가중치 } 로 저장한다. DFS 두 번 하는 방법: 트리 먼저 만들고, 중심을 옮길지 말지 결정 0을 기준으로 모든 정점의 거리 합을 계산한 후 0보다 하위인 정점이 중앙 정점이 될 수 있는지 판단 1. 0에서 DFS, 모든 정점과 0사이의 거리 합 계산 이때 각 .. 2021. 7. 30. BOJ2549 루빅의 사각형 2549번 루빅의 사각형 4×4 격자판이 있다. 행을 한 개 골라 아래쪽으로 k번(1≤k≤3) 움직이거나 열을 한 개 골라 오른쪽으로 k번(1≤k≤3) 움직이는 것을 한 번 움직인다고 한다. 격자판의 숫자가 주어질 때, 최소 횟수로 격자판을 움직여 1부터 16까지 순서대로 배열된 격자판으로 만드는 횟수(≤7)와 방법을 출력한다. 일단은, 되는대로 BFS를 돌려봤지만 역시 메모리 초과로 통과할 수 없었다. 한 번 움직이는 경우의 수는 8(행/열 개수)*3(k 개수)였고 아무리 정답이 7번 이내로 나온다 해도 24^7개의 경우를 확인하려니 당연히,, 몇 가지 최적화로 가짓수를 줄여봤지만 그래도 메모리초과였다. 방법 1. BFS + 양방향 탐색 + map BFS로 찾되 양방향으로 탐색하기로 했다. 주어진 상태.. 2021. 7. 25. SCC SCC : 강한 연결 요소 strongly connected components 그래프 내 vertex 중 서로 간의 경로가 양방향 모두 존재하는 vertex들의 집합 X⊂G s.t. ∀a, b∈X, ∃ paths both a→b, b→a DFS와 스택이 핵심이다. 방문 지점의 order(몇 번째로 방문했는지)를 이용한다. DFS함수의 리턴 값은 현재 노드에서 도달할 수 있는 지점 중 가장 먼저 방문한 지점의 방문 순서이다. DFS(cur) = par = cur에서 도달할 수 있는 지점의 ord 중 최솟값 ord[v] v 방문 순서 fin[v] v 방문 완료 여부 = v가 속하는 SCC를 찾았는지? 현재 방문한 지점을 cur, 다음에 방문할 지점을 nxt라 하자. nxt는 다음 세 가지 경우 중 하나에 .. 2021. 4. 13. 이전 1 다음
