dh_0e

아이돌 (백준 3648번) 2-SAT 문제에 상근(1번 참가자)이가 항상 합격할 수 있는 경우가 있는지를 찾는 문제. 풀이 과정상근이가 포함된 SCC 집합을 true로 만들고 각 SCC 집합 관계가 맞는지 확인하는 방식은 너무 복잡해짐.상근이가 항상 합격해야 한다는 심사위원의 평가를 하나 만들면 된다. vec[ch(-1)].push_back(1) → (1, 1) 의 평가를 하나 추가하여 1번 참가자가 무조건 합격하게끔 만드는 식으로 한정지어줌#include#include#include#include#includeusing namespace std;stack st;vector vec[2'001];bool vi[2'001];int p[2'001];int id = 0, scc = 0;auto ch = [](i..

2-SAT - 4 (백준 11281번) 2-SAT-3 에서 식을 true로 만들 수 있는 변수들의 값을 출력하면 되는 문제. 풀이 과정2-SAT 문제에서 변수 값을 정할 때 위상 정렬(Topological Sort) 순서를 거꾸로 따라감그래프에서 A → B 라는 건, A를 결정해야 B를 알 수 있다는 뜻이며 이게 위상 정렬 순서가 된다(A가 B보다 앞에 옴).근데 만약 우리가 A를 참(True)으로 정했는데, 이게 어찌어찌 흘러가서 A ⇒ ... ⇒ ¬A 라는 모순을 만들면 식이 성립할 수 없다.이런 모순을 피하는 가장 안전한 방법은, 함의 관계의 맨 끝, 즉 종착지부터 값을 정하는 것. 종착지는 위상 정렬 순서에서 가장 나중에 오므로, 위상 정렬의 역순으로 거슬러 올라가면서 값을 결정한다. 이렇게 하..

2-SAT - 3 (백준 11280번) SCC 알고리즘 문제를 풀다가 만난 또 다른 알고리즘인 2-SAT 기본 문제이다. 처음에 태그를 보지 않고, 2-CNF 식을 그래프로 만들어보려고 하루 이상을 고민했지만 비슷하게나마 접근하는데에 그쳤다. 2-SAT 문제에 대한 설명은 아래 블로그를 보고 공부했다. 2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)안녕하세요. 이번에 강의할 내용은 2-SAT(2-Satisfiability)이라는 좀 생소할 수 있는 내용입니다! 이...blog.naver.com먼저 명제를 단방향 간선들로 바꿔서 그래프를 만들어준 뒤, 타잔 알고리즘으로 SCC 구현을 한다. 이후, 각 변수에 대해 자신의 not 형 변수가 같은 SCC에 들어있으면..

도미노 (백준 4196번) 풀이 과정 SCC 변형 문제로 타잔 알고리즘으로 해결하였다.p배열을 구한 뒤, SCC 간 위상 관계를 생각해보면 사이클이 없는 트리처럼 생각할 수 있다. 이 트리의 root 개수를 구해주면 된다.타잔 알고리즘으로 각 연결 요소 집합(p배열) 구한다.각 vertex의 edge를 탐색하여 자신이 넘어뜨릴 수 있는 다른 도미노의 집합(B)이 자신의 집합(A)과 다르면 B는 다른 집합에 의해 넘어지는(root가 아닌) 도미노 집합임을 저장한다. (if (p[i] != p[next])vi_2[p[next]] = 1;)집합에 존재하는 모든 vertex가 다른 도미노에 의해 넘어지지 않는 집합(root)의 개수를 구한다. #include#include#include#include#inclu..

Strongly Connected Component (백준 2150번) Strongly Connected Component(강한 연결 요소) 알고리즘 기본 문제. 모르고 풀이를 떠올렸을 때, dfs로 비슷하게까지는 생각했는데, 알아보니 타잔 알고리즘이나 코사라주 알고리즘을 사용해야 했고, 비교적 간단한 타잔 알고리즘을 사용해 풀었다. id를 사용해서 깊이만큼 초기값을 가지는 것, 다음 vertex의 id값을 받아서 내 parent 값보다 작으면 갱신한다는 부분이 킥이었다.아래 블로그에 두 알고리즘을 자세히 설명되어있다. SCC - 강한 연결 요소 찾기강한 연결 요소 (SCC, Strongly Connected Component) 란, 유향 그래프에서 정점의 부분집합이 부분집합 내의 다른 모든 정점에 대해..