https://www.acmicpc.net/problem/2519 2-SAT 관련 문제입니다. 명제를 정의하는데 시간을 많이 썼지만, 실질적인 구현은 크게 어렵지 않습니다. 주어진 문제를 보면, N명의 사람들이 3개의 막대기를 갖고 있고, 각자 최대 1개의 막대기를 뺄 수 있습니다. 이 때 막대기를 뺀 상태에서 모든 막대기가 겹치는지, 겹치지 않는다면 무엇을 뺀 것인지를 구하는 문제입니다. 문제를 2-SAT 문제로 대입하면 다음과 같습니다. 2-SAT : (x1 or x2) and (x3 or x4) and .... 와 같은 CNF 에서 명제가 true가 되는 x1, x2, ... 의 해를 구할 수 있는가문제 : 모든 막대기들이 겹치지 않는가 즉, clause에 해당하는 것은 각 막대기들이 겹칠 때 ..
https://www.acmicpc.net/problem/112812-SAT 문제를 공부해보았습니다. 2-SAT문제는 아래와 같습니다.(x or y) : clause 를 대상으로 CNF 형태 (모두 and로 묶여 있는 형태) 에 대해 해가 존재하는 지를 판단 (만족하는 해가 있는가?) 하는 satisfiability 문제입니다. x or y == ~x -> yx or y == y or x == ~y -> x 이므로 CNF로 주어진 식을 아래와 같이 그래프로 표현할 수 있습니다. ex) (~x1 or x2) and (~x2 or x3) and (x1 or x3) and (x3 or x2) x1 -> x2, ~x2 -> ~x1x2 -> x3, ~x3 -> ~x2~x1 -> x3, ~x3 -> x1~x3 ..
https://www.acmicpc.net/problem/4196 SCC를 활용한 문제입니다. 도미노 관계가 주어졌을 때, 최소 몇 개의 도미노를 넘어트려야 전체 도미노가 쓰러지는 지를 계산합니다. SCC를 계산하면, 각 SCC는 사이클을 이루므로 아무거나 넘어트려도 됩니다. 그리고 SCC를 구성하는 컴포넌트들을 하나의 큰 노드로 본다면, 그 노드들 중 indegree 엣지가 0인 것들만 넘어트린다면 전체가 넘어지고, 이것이 최소 개수입니다. indegree 엣지가 0인 것들은, 입력된 그래프의 엣지를 대상으로, from, to 노드가 동일 컴포넌트인지 아닌지를 체크하면 알 수 있습니다. 즉, 컴포넌트 번호가 다르다면, 엣지로 연결된 두 노드는 다른 컴포넌트에 있는 것이고, 이는 to 노드가 포함..
https://www.acmicpc.net/problem/11409 열혈강호 5와 마찬가지로 mcmf 알고리즘 문제입니다. mcmf 기본 설명 및 코드 : https://ghqls0210.tistory.com/377 백준 11408 열혈강호 5https://www.acmicpc.net/problem/11408 MCMF 알고리즘을 공부할 수 있는 문제였습니다. MCMF 알고리즘이란, 최소 비용으로 최대 유량을 보내도록 값을 찾는 알고리즘입니다. 즉, 엣지마다 비용이 정해져ghqls0210.tistory.com 단, 일반적인 mcmf와 달리, 최대 비용, 최대 유량을 구합니다. 이는 비용을 처음부터 음수로 처리하여 최소 비용 최대 유량을 구하는 것과 동일하게 계산하면, 음수 중 최소값이므로, 최종 계산 시..
https://www.acmicpc.net/problem/11408 MCMF 알고리즘을 공부할 수 있는 문제였습니다. MCMF 알고리즘이란, 최소 비용으로 최대 유량을 보내도록 값을 찾는 알고리즘입니다. 즉, 엣지마다 비용이 정해져 있다면, 최대 유량을 보내는 방법이 여러 가지일텐데, 그 중 가장 최소 비용 값을 찾는 것입니다. 전체 비용은 sum(엣지의 비용 * 엣지의 유량) 으로 계산됩니다. MCMF 알고리즘과 관련된 문제들은 edmonds-karp에 spfa를 적용하여 푸는 것으로 알려져 있습니다.즉, edmonds-karp로 최대 유량을 계산할 때, 단순히 증가 경로 상에 부모 노드를 고르는 것이 아닌, 최소 비용을 갖는 엣지를 통해 부모를 선택합니다. 이 때 최소 비용 경로 계산을 spfa로..