devbelly

문제 www.acmicpc.net/problem/17038 알고리즘 2-SAT 풀이 소들마다 두 개의 목초지에서 식사를 하고, 소들의 식성은 두가지로 나뉩니다. 한 식성은 두 목초지의 풀이 같아야만 하고, 다른 식성은 두 목초지의 풀이 달라야만 식사를 합니다. 이 때, 가능한 목초지의 경우의 수를 구하는 문제입니다. 두 종류의 풀이 주어지는 점, 이를 동시에 만족하도록 하는 점에서 2-SAT임을 파악하여 풀도록 합시다. 한 종류의 풀을 True, 다른 종류의 풀을 False로 설정하고 SCC를 사용합니다. 입력에서 10개의 목초지가 주어지고 5마리의 소의 입력이 다음과 같다고 생각해봅시다. S 1 2 S 3 4 S 5 6 S 7 8 S 9 10 이 경우는 32가지가 정답인 것을 알 수 있습니다. 1 2 ..

문제 https://www.acmicpc.net/problem/11281 알고리즘 2-SAT 풀이 이 문제에서 실제 해까지 찾아서 출력하는 문제입니다. SCC 이후 하나의 간선을 구성하는 두 정점을 살펴봅시다. 앞서 살펴본 바와 같이 u->v를 만족하기 위해선 not u 일 땐 v가 무엇이 와도 상관이 없으나 True u 일 땐 2-CNF에서의 절을 만족하기 위해 v가 True임이 강제됩니다. 즉 우리는 위상 정렬상 빠른 쪽에 위치한 정점을 False로 평가하는 것이 True로 평가하는 것에 비해 항상 이득임을 알 수 있습니다. 코드 #include #define rep(i,n) for(int i=0;i u >> v; OR(u, v); } discovered = sccid = vector(N

문제 https://www.acmicpc.net/problem/1108 알고리즘 SCC 풀이 점수가 무한대로 늘어나는 것을 방지하기 위해 두 정점에 대해 직간접적 연결이 없을 때에만 점수를 더해준다고 합니다. 직간접 연결을 확인하려면 그래프에서 사이클을 확인해야 하고 사이클을 확인하는 알고리즘인 SCC를 떠올릴 수 있습니다. SCC알고리즘 사용 이후, 모든 간선을 검사하며 두 정점의 $sccid$가 다르다면 $sccadj$에 실제 간선을 추가해줍시다. 이 이유는 하나의 SCC로 묶인 정점들끼리도 점수가 다를 수 있기 때문입니다. 단, $cache$를 갱신하는 과정은 위상정렬상 앞에 있는 순서부터 뒤에 있는 순서로 갱신해나가야 하므로, vector형태를 사용한 것에 주목합시다. 예를 들어 scc_adj[a..

문제 https://www.acmicpc.net/problem/11097 알고리즘 SCC 풀이 처음에 문제만 읽어서는 SCC라는 것을 알아채기가 힘들었던 문제입니다. 감이 잡히지 않으므로 2번 예제를 직접 그려보도록 합시다. 그림을 그려본다면 답에 해당하는 간선이 두 가지 종류임을 알 수 있습니다. 첫 번째는 하나의 SCC에서 다른 SCC를 잇는 외부 간선입니다. 두 번째는 각각의 SCC내부를 잇는 내부간선입니다. 이제 각각의 처리방법에 대해 생각해봅시다. SCC알고리즘의 작동방식을 생각해본다면 하나의 컴포넌트로 묶을 때 스택에서 차례대로 하나씩 꺼낸 후 묶는 것을 알 수 있습니다. 즉 스택에서 연속된 값은 서로를 잇는 내부 간선들임을 알 수 있습니다. 즉 스택에서 꺼내며 $sccid$를 부여 할 때 내..

문제 https://www.acmicpc.net/problem/4013 알고리즘 SCC 풀이 여행 계획 세우기 문제와 거의 비슷합니다. 방문한 도시를 또 방문할 수 있다는 점에서 사이클이 존재함을 알 수 있고, 하나의 사이클안에 있는 ATM은 전부 얻을 수 있는 돈이므로 SCC를 통해 하나의 큰 정점으로 표현 가능합니다. DAG위에서 위상정렬 순서상 빠른 정점부터 얻을 수 있는 최대 금액을 갱신해나가면 됩니다. 이는 $SC$값을 역으로 순회하면 해결 가능합니다. 단, 위 문제와는 다른 점이 있다면 도착 정점이 여러 개라는 점입니다. 사용하는 변수가 많으므로 추가적인 변수들은 아래에 정리해두니, 코드를 보실 때 참고하시면 좋습니다. $isres[i]$= $i$교차로에 레스토랑이 있을 때, True $mon..

문제 https://www.acmicpc.net/problem/4196 알고리즘 SCC 풀이 손으로 넘어뜨려야 한다는 것은 자신을 밀어주는 도미노가 없다는 뜻이죠. 그래프로 나타낸다면 자신을 가리키는 간선이 없습니다. 즉, 차수가 0인 컴포넌트의 개수가 정답입니다. SCC를 사용해 그래프를 DAG로 만든 후 모든 간선들을 검사하며 양쪽 정점의 $sccid$가 다르다면 한쪽 정점의 차수를 카운트 해줍니다. 이후 $ind$ 를 순회하며 값이 0이라면 $ans$를 증가시켜주면 됩니다. 코드 #include #define rep(i,n) for(int i=0;i TC; while (TC--) { cin >> N >> M; VC = SC = 0; adj.clear(); sccid.clear(); discovere..

문제 https://www.acmicpc.net/problem/2152 알고리즘 SCC 풀이 SCC는 그래프를 DAG로 바꾸며 각 컴포넌트의 크기를 최대로 묶어줍니다. 최대 도시를 구한다는 점과 시작 도시와 도착 도시가 있다는 점은 SCC와 잘 어울리죠. DAG로 그래프를 바꾼 후에는 DAG상에서 차수가 낮은 컴포넌트부터 차수가 높은 컴포넌트를 갱신해줍니다. 즉 위상정렬 순서로 갱신해줍니다. 유의할 점 중 하나는 SCC알고리즘을 사용하게 되면 $sccid$의 역순이 위상 정렬 순서와 동일합니다. 다시 말해 $sccid$ 의 값이 작다면 위상정렬 순서상 뒤에 있고, $sccid$값이 크다면 위상 정렬순서상 앞에 있음을 의미합니다. 굳이 위상 정렬 알고리즘을 사용해서 순서를 배치할 필요가 없습니다. dfs ..