본문 바로가기

SCC

BOJ 25392 - 사건의 지평선 (D3) 사용 알고리즘 Segment Tree + SCC + 위상정렬 dp 풀이 일단 어떻게 했는진 몰라도 i->L~R 간선을 잘 이어줬다고 치자. 무한 번 표시된다 = 사이클에서 돌고 있다는 의미이다. 따라서 사이클 내부에서 가장 큰 원소를 찾으면 그 사이클 내부에서의 정답이 된다. 단 어떤 사이클 u에서 v로 간선이 있는경우, u에서의 정답은 max(u 내부에서의 정답, v 내부에서의 정답)이다. 따라서 위상정렬 dp로 순차적으로 사이클에서의 최댓값을 결정해나가면 된다. 이제 i->L~R 간선을 깔끔하게 처리하는 법만 생각하면 된다. L~R은 구간이다. 구간 크기가 O(N)이므로 간선이 최대 O(N^2)개가 생긴다. 그렇다면 구간을 O(logN) 정도로 표현할 수 있다면 추가해야 하는 간선은 O(NlogN)개.. 더보기
BOJ 4013 - ATM (P2) https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 사용 알고리즘 SCC + 위상정렬 DP 풀이 ATM에서 현금을 인출할 때, 어떤 정점에서 사이클이 존재한다면 그 사이클을 쭉 돌면서 사이클에 속하는 모든 정점의 ATM을 이용할 수 있다. 따라서 사이클 내의 정점들을 묶어 생각할 수 있고, 하나의 SCC로 묶어줄 수 있음을 알 수 있다. 예제 그래프이다. 위에 적힌 숫자는 ATM에서 인출할 수 있는 현금이고, 색칠된 숫자는 그 정점에.. 더보기
BOJ 1739 - 도로 정비하기 티어: D5 (체감 D5) 알고리즘: 2-SAT 여기서는 가로 도로를 행, 세로 도로를 열로 표기한다. 어떤 버스가 (a,b)에서 (c,d)로 갈려면 다음 2가지 중 하나를 이용해야 한다. (도로를 최대 2개밖에 이용하지 못하기 때문) 1. a행, d열을 이용한다. 2. c행, b열을 이용한다. 일단 a≠c, b≠d라고 가정하고 예제 1의 테스트케이스 1을 보자. 위 그림은 테스트케이스 1번에서 (1,1)에서 (6,6)으로 가는 버스를 나타낸 것이다. 빨간색 경로는 1행과 6열을 이용해서 (1,1)에서 (6,6)으로 간다. 파란색 경로는 1열과 6행을 이용해서 (1,1)에서 (6,6)으로 간다. 위를 통해 (a,b)에서 (c,d)로 갈려면 a행, d열을 이용하거나 c행, b열을 이용해야 함을 알 수 있다.. 더보기

티스토리툴바