문제 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 설명 그 간선을 제거했을 때 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 단절선이라 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 먼저 간선 정보를 저장할 CutLine 클래스를 만들고 단절선을 저장할 배열인 cutList를 만든다. 나중에 단절선을 사전순으로 출력해야 하므로 Comparable 인..
문제 https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 설명 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 각 정점들마다 방문 순서를 부여하기 위한 visited[] 배열과 단절점인지 판단하기 위한 isCutPoint[] 배열을 선언하고 정점간의 연결관계를 입력받아 인접리스트를 만들어준다. 방문하지 않은 정점을 시작으로 DFS 탐색을 수행하여 order를 저장하고 단절..
문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 설명 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력해야 한다. 각 정점의 방문 여부를 체크하기 위한 check 배열과 각 정점의 깊이를 저장할 depth 배열을 만든다. 그리고 각 정점의 \(2^k\) 번째 부모를 저장하기 위해 parent[18][] 배열을 만든다...
최소 공통 조상 (Lowest Common Ancestor / LCA) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 정점 A 혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점 위의 그림에서 13번 정점과 15번 정점의 최소 공통 조상은 5번 정점이 된다. 최소 공통 조상 구하기 선형 탐색 : \(O(depth) = O(N)\) 1. 최상위 조상 정점을 시작으로 DFS 또는 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. 2. 최소 공통 조상을 찾을 두 정점을 확인한다. 3. 먼저 두 정점의 깊이가 같아질 때까지 각각 부모를 따라 거슬러 올라간다. 4. 이때, 가리키는 정점이 다르다면 다시 각각 부모를 따라 하..
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/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 설명 Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다. 단어 사전을 만들어 단어를 빠르게 검색할 수 있는 방법으로는 트라이가 있다. 트라이를 구현하기 위해 TrieNode 클래스를 만들고 필요한 메서드들을 만든다. class ..
문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 설명 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다. 처음 위치인 (0, 0)에서 시작하여 DFS을 진행한다. 나중에 사이클이 만들어지는지 확인하기 위한 visited 배열과 같은 좌표를 또 방문할 때 가지치기하기 위한 dp 배열을 만든다. DFS를 진행하..
문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 설명 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다. 암호를 이루는 알파벳은 암호에서 증가하는 순서로 배열되어 있다. 먼저, 입력받은 알파벳을 알파벳 순서대로 정렬한다. 자릿수는 L이고 알파벳 수는 C이므로 암호의 첫 알파벳은 input[0] ~ input[C-L] 이 될 수 있다. 암호의 길이를 나타내는 length, 모음의 개수를..
