최소 공통 조상 (Lowest Common Ancestor / LCA) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 정점 A 혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점 위의 그림에서 13번 정점과 15번 정점의 최소 공통 조상은 5번 정점이 된다. 최소 공통 조상 구하기 선형 탐색 : \(O(depth) = O(N)\) 1. 최상위 조상 정점을 시작으로 DFS 또는 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. 2. 최소 공통 조상을 찾을 두 정점을 확인한다. 3. 먼저 두 정점의 깊이가 같아질 때까지 각각 부모를 따라 거슬러 올라간다. 4. 이때, 가리키는 정점이 다르다면 다시 각각 부모를 따라 하..
문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 설명 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 여러 개의 건물을 동시에 지을 수 있다. 건물을 짓는데 우선순위가 있으므로 이는 DAG로 나타낼 수 있다. 먼저 건물을 짓는데 걸리는 시간과 후행자로 가지는 건물 번호 리스트를 저장할 Build 클래스를 만든다. class Build { int time; ArrayList successor; public Bui..
DAG (Directed Acyclic Graph) DAG는 순환을 가지지 않는 방향 그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG 구조를 가진다. DAG에서 어떤 정점 \(v_i \in V, v_j \in V\) 에 대해서 \(v_i\) 에서 \(v_j\) 로의 경로가 존재하면, \(v_i\) 는 \(v_j\) 의 선행자이고 \(v_j\) 는 \(v_i\) 의 후행자이다. DAG에서 어떤 정점 \(v_i \in V, v_j \in V\) 에 대해서 \(v_i\) 에서 \(v_j\) 로의 간선이 존재하면, \(v_i\) 는 \(v_j\) 의 즉각 선행자이고 \(v_j\) 는 \(v_i\) 의 즉각 후행자이다. 위상정렬 DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것을..
문제 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 설명 1 ≤ i < j ≤ M인 i와 j를 고른 뒤, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 1,000,000보다 작거나 같은 자연수인 N을 위의 연산을 K번 하는데 이는 바뀐 수도 1,000,000보다 작거나 같은 수라는 뜻이므로 1,000,000 크기의 visited 배열을 만들어 현재 depth에서 이미 만들어진 수는 또다시 연산을 수행하지 않도록 한다 그리고, queue를 만들어 처음에 N을 넣고 BF..
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 설명 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. 물도 매 분마다 비어있는 칸으로 확장하는데 물이 있는 칸과 인접해있는 비어있는 칸은 물이 차게 된다. 고슴도치는 물로 차있는 칸으로 이동할 수 없고 물은 비버의 소굴로 이동할 수 없다. 둘 다 돌을 통과할 수 없다. 비어있는 곳, 물이 차있는 지역, 돌, 비버의 굴, 고슴도치의 위치를 저장할 map[][]을 만들어 저장..
DFS DFS(Depth-First Search)는 깊이 우선 탐색이라고 부른다. 한 경로로 최대한 깊숙하게 들어가서 탐색한 후 다시 돌아가 다른 경로를 탐색하는 방식 일반적으로 재귀함수를 이용하여 구현하며 Stack을 이용하여 구현하기도 함 구조상 Stack Overflow에 유의해야 함 DFS 활용 : 백트랙킹, 단절선 찾기, 위상정렬, 사이클 찾기 등 DFS 구현 1. 체크인 2. 목적지인가? 3. 연결된 곳을 순회 4. 갈 수 있는가? 5. 간다 6. 체크아웃 static int[][] graph; static boolean[] visited; static void dfs(int index) { // 1. 체크인 visited[index] = true; // 2. 목적지인가? if (종료조건) {..
