Tags

5 pages

SCC

[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

섬 내부 도로망은 선분 도로가 교차하지 않는 평면 그래프이므로, SCC 압축 DAG에서 각 컴포넌트가 도달할 수 있는 동쪽 경계 정점 집합은 y좌표 기준 연속 구간이 됩니다. 이를 이용해 동쪽 경계 정점(서쪽에서 실제로 도달 가능한 것만)을 y 오름차순으로 인덱싱하고, 자식 구간을 부모로 병합하는 역위상 전파로 각 서쪽 정점의 답(서쪽 정점에서 도달 가능한 동쪽 정점 수)을 O(n+m)에 계산합니다. 구현은 반복형 Kosaraju + 압축 그래프 위상정렬 기반입니다.
[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

[Algorithm] C++ 백준 14737번 Dev, Please Add This!

격자에서 공을 상하좌우로 굴려 벽이나 가장자리에 닿을 때까지 이동하는 퍼즐에서, 모든 별을 하나의 플레이 순서로 획득할 수 있는지 판정한다. 단순 커버리지가 아니라 이동 순서 제약이 존재하므로 셀 단위 이동을 단방향 그래프로 모델링하고, 강한 연결 요소(SCC)로 압축한 DAG에서 상호 비가역(서로 도달 불가)한 컴포넌트 쌍의 동시 방문을 금지하는 제약과 각 별이 있는 칸의 행/열 중 하나의 정지 컴포넌트를 반드시 방문해야 한다는 제약을 2-SAT으로 구성해 모순 여부로 YES/NO를 결정한다. Kosaraju로 SCC를 구하고 DAG 도달성은 비트셋 DP로 처리하여 50×50까지 빠르게 동작한다.
[Algorithm] C++ 백준 14737번 Dev, Please Add This!