SCC

[백준 15559] 내 선물을 받아줘 (C++)

15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 강한 연결 요소 임의의 칸에서 출발해서 다시 자신의 칸으로 되돌아 올 수 있으면 해당 루트의 아무 지점에 선물을 놓아도 선물을 가져갈 수 있다. 따라서 각 칸의 scc번호를 구한다. scc번호를 구하고 scc그래프를 만드는데 역방향으로 만드는게 중요하다. 하나의 SCC집합 내부에선 어떤 칸에 놓던지 선물을 가져갈 수 있는 성질을 활용하면 된다. SCC의 outdegree가 0이면 해당 SCC에서 다른 SCC로 갈 수 없다..

[백준 4013] ATM C++

4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 강한 연결 요소, 다이나믹 프로그래밍 처음 풀어보는 플레2 문제였다. 풀려서 기분이 매우 좋았음 우선 모든 정점들을 dfs로 순회하며 각 정점의 SCC를 구해줬다. SCC를 구하면서 해당 SCC에 속하는 현금의 양 + 해당 SCC에 레스토랑이 있는지 판단해 주었다. 구한 SCC를 통해서 SCC 그래프를 만들어 주었다. -> make_sccgraph() 이제 DP문제로 바뀌게 되었다. 시작점의 SCC에서 출발해, 레스토랑이 있는 SCC까지의 거리의 ..

[백준 3977] 축구 전술 C++

3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 도미노 문제와 매우 비슷한 문제이다. 이 문장을 통해서 SCC임을 알 수 있다. 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으..

강한 연결 요소 (SCC) - 타잔 알고리즘

[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 학교 알고리즘 수업 때 코사라주 알고리즘을 활용한 SCC풀이법을 배웠다. 하지만 구글링을 해보니 코사라주 알고리즘보다는 타잔 알고리즘이 구현이 어렵지만 활용도가 더 높다고 해서 공부해 보았다. 타잔 알고리즘 1번 정점에서 dfs를 시작해 2, 3, 4번 정점을 순서대로 방문했다고 하자. 타잔 알고리즘에서는 방문할 때마다 임의의 sta..

[백준 6543] 그래프의 싱크 C++

6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net 강한 연결 요소 코사라주 알고리즘 1. 문제 해결 아이디어 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 이전에 포스팅 했던 문제에서 사..