mojo's Blog

문제 링크 => 6086번: 최대 유량 (acmicpc.net) 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 최대 유량 문제이다. Edmond-carp Algorithm 을 이용하여 해결하였다. 문제에서 활용될 노드는 'A' ~ 'Z', 'a' ~ 'z' 이므로 총 52개의 노드가 필요하다. Input 을 보면 from, to, capacity 가 제공되는데 여기서 from, to 가 중복해서 나타나는 경우가 존재한다. 따라서 capacity를 노드에서 노드로 이동하는 2차원 배열 c[x][..

문제 링크 => 10891번: Cactus? Not cactus? (acmicpc.net) 10891번: Cactus? Not cactus? 첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정 www.acmicpc.net BCC를 이용한 문제이다. Cactus 임을 판단하기 위해서 두 개의 조건을 만족해야 한다. 1. BCC로 묶인 간선의 갯수가 3개 이상인 경우 BCC로 묶여 있는 정점들의 갯수와 동일한지 파악해야 한다. 2. 1번 조건을 고려할 때, 간선의 갯수가 3개 이상으로 묶인 BCC 중에서 임의의 정점이 2개 이상인 경우 즉, 임의의 ..

문제 링크 => 6672번: Electricity (acmicpc.net) 6672번: Electricity Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there i www.acmicpc.net BCC(Biconnected Component) 문제이다. 연결된 노드들 사이에서 임의의 노드를 하나 제거할 때, ..

문제 링크 => 11400번: 단절선 (acmicpc.net) 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net DFS 트리를 이용하여 단절선을 찾아내는 문제이다. [백준 11266] 단절점 :: M - J - C (tistory.com) 에서 단절점을 구하는 과정에서 Case 2 를 고려하지 않고 Case 1 에서 dfn[cur] < low[child] 을 만족하는 경우에 cur ~ child 로 이어진 간선은 단절선이다. 그리고 단절선을 구하고 주의해야 할점은 문제에서 단절선을 사..

문제 링크 => 11266번: 단절점 (acmicpc.net) 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net DFS 트리를 이용하여 단절점을 찾아내는 문제이다. Tarjan's Algorithm 을 이용하여 노드별로 dfs로 방문하면서 매겨지는 dfn값과 해당 노드에서 최소 dfn 값 (low)을 찾는 과정 속에서 단절점을 찾아내는 방법은 다음과 같다. case 1. 자식노드가 dfn 값이 매겨지지 않은 경우 : dfn[cur] 2 : low[2] = dfn[2] = 2 (2) 2..

문제 링크 => 2848번: 알고스팟어 (acmicpc.net) 2848번: 알고스팟어 첫째 줄에 알고스팟어의 알파벳 순서를 출력한다. 만약, 올바른 순서가 없다면 "!"를, 가능한 순서가 한 개 이상이라면 "?"를 출력한다. www.acmicpc.net 위상정렬 문제이다. 알고스팟어의 알파벳 사전 순으로 정렬되어 있는 단어의 목록이 주어질 때, 알고스팟어의 알파벳을 순서대로 구해야 하는 문제이다. 접근 방법은 다음과 같다. 1. 문자열들의 모든 경우를 각각 2개씩 비교하면서 확실하게 알파벳의 순서가 변경되는 지점을 찾고 위상정렬을 위한 inDegree 세팅을 해준다. 알파벳의 순서가 변경되는 지점을 찾는 방법을 예제 입력 1 을 통해서 알아보도록 한다. s1 : ula, s2 : uka => s1[1]..