알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2152 2152번: 여행 계획 세우기첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공www.acmicpc.netSCC 알고리즘과 BFS, DP가 사용된 문제입니다.S도시에서 시작해 T도시에 도착할 때, 여행할 수 있는 최대 도시 수를 구하는 문제입니다. 도시는 한번만 방문 가능한 것이 아닌 여러번 방문할수 있습니다.(여러 번 방문했다고 해도 방문한 도시의 수는 1개만 증가합니다.) 만약, ’도시들 중에 순환이 가능한 도시들이 있다면 해당 도시들을 하나의 그룹으..

문제 링크입니다. https://www.acmicpc.net/problem/4013 4013번: ATM첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차www.acmicpc.netSCC 알고리즘과 위상정렬 알고리즘, 약간의 DP가 섞인 문제입니다. 도시와 교차로가 주어질 때, 시작 도시에서 아무 레스토랑까지 얻을 수 있는 현금의 최대 액수를 구하는 문제입니다. 한 도시를 여러 번 도달 가능하는 점이 있기에 서로 연결되어 순환하는 도시들은 전부 현금을 가져올 수 있게 됩니다. 문제에서는 (1, 2, 4)번 도시와 같은 집합이 해당합니다. 그렇다면,..

문제 링크입니다. 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강한 연결 요소 알고리즘(SCC)를 사용해 푸는 문제입니다.문제에서 SCC가 두 개의 정점 u, v에 대해서 u -> v, v -> u로 가는 경로가 모두 존재하는 경우를 의미한다고 알려주지만,쉽게 말하자면, 그래프의 정점간 순환이 가능한 부분을 의미한다고 생각하면 편합니다.주어진 그래프를 봤을 때, (a, b,..

문제 링크입니다. https://www.acmicpc.net/problem/4196 4196번: 도미노도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러www.acmicpc.netSCC(강한 연결 요소) 알고리즘을 이용해 위상정렬로 푸는 문제였습니다.참고한 SCC 알고리즘 설명 https://hyeo-noo.tistory.com/m/130 강한 연결 요소 (SCC) - 타잔 알고리즘[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E..