CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 난이도: 플래티넘 4 사용언어: JAVA 풀이 SCC와 위상 정렬을 함께 고려해야 하는 문제입니다. 언뜻보면 SCC 문제가 아닌것 같지만, 도미노들의 SCC를 구하고 구해진 SCC들간에 위상 정렬을 해서 다른 SCC로 부터 영향을 받지 않는 SCC들을 골라내면 정답을 도출 할 수 있습니다. SCC의 풀이 중 코사라주 알고리즘을 이용했고, 코사라주 알고..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 난이도: 플래티넘 5 사용언어: JAVA 풀이 이름 그대로 Strongly Connected Component(SCC) 문제의 가장 기본적인 유형입니다. 저는 코사라주 알고리즘을 이용하여 문제를 해결하였습니다. 코사라주 알고리즘은 아래의 링크에서 더 자세하게 확인..