그냥 하는 노트와 메모장

* BOJ 11097 도시계획 (https://www.acmicpc.net/problem/11097) [ 분류 - SCC(Strongly connected components) ] 다소 까다로운 문제? 였다. 반면 접근 방식이 매우 여러가지라 아래 해설도 그 중 하나라고 봐주시면 되시겠당 :) 문제가 물어보는 것은 플로이드의 결과라고 생각할 수 있는 인접 행렬이 주어졌을 때, 이를 구성할 수 있는 가장 적은 도로를 쓰는 도로망을 구성하는 것이다. 그리고 일방통행 도로이기 때문에 방향 그래프인 것을 알 수 있다. 이 문제를 "최대한 도로를 지우는" 과정으로 볼 수 있다. 인접 행렬에서 지울 수 있는 도로를 모두 지워야 최소 크기의 도로망을 구성할 수 있기 때문이다. 임의의 정점에 대해서 생각해보자. 정점 ..

* 강한 연결 요소(SCC, Strongly connected components) 문제들 Topological sort, dynamic programming, DSU 등 다양한 알고리즘과 연결하여 풀 수 있는 문제들을 Random하게 소개해 보겠당. 1. 백준 온라인 저지 1-1. Strongly connected component(https://www.acmicpc.net/problem/2150) 기본적인 SCC 문제다. 모든 SCC를 저장하고 이를 정렬하여 출력하면 된다. - 코드 #include #include #include #include using namespace std; int min_v(int a, int b) { return a < b ? a : b; } vector adj; int ..

* 강한 연결 요소 (SCC, Strongly connected components) 방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 있다고 말한다. if vertex u has paths to vertex v and also v has paths to u, either u and v are involved in same SCC. 이 SCC 집합은 하나의 component 내에 여러개가 생길 수 있다. 아래 그림을 보면 하나의 component에 대해 3개의 SCC가 있음을 직관적으로 알 수 있다. SCC의 특성 중 하나는 SSC 간의 방향 그래프를 그려보면 DAG가 나온다는 것이다. 이는 연역적으로 정리가 가능하다. 1. 현재 구성할 수 있는..