문제 풀이/백준 (BOJ)

[백준/BOJ] 4013번: ATM ( SCC, 위상 정렬 응용 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/4013 풀이이 문제는 출발 지점으로부터 방문할 수 있는 레스토랑까지 가는 동안 구할 수 있는 금액의 최대 값을 출력하는 문제입니다. 이 문제를 풀기 어렵게 만드는 것은, 문제를 그래프로 변경 시, 그래프에 순환 경로가 존재한다는 것입니다.그래서, 우선 순환 경로를 제거합니다.그 방법은 강한 결합 요소( SCC )를 구해서, 그 요소의 정점들을 하나의 정점으로 변경하는 것입니다.그렇게 되면, 원래의 그래프가 순환 경로가 없는 방향 그래프( DAG, Directed Acyclic Graph )가 됩니다.  이 과정을 코드로 작성하면 다음과 같습니다. 여기선, SCC를 구하기 위해 타잔( Tarjan ) 알고리즘을 사용하였습니다..

2024. 7. 17.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2150번: Strongly Connected Component ( SCC 타잔 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2150 풀이이 문제는 방향 그래프가 주어졌을 때, 그 안에 존재하는 강한 연결 요소( Strongly Connected Component, SCC )를 구해 출력하는 문제입니다. 강한 연결 요소는 방향 그래프에서 임의의 두 정점을 선택하더라도, 두 정점 간에 경로가 존재하는 최대 부분 집합을 말합니다. 이러한 강한 연결 요소를 구하는 알고리즘이 두 가지 있는데,하나는 코사라주( Kosaraju ) 알고리즘이고, 다른 하나는 타잔( Tarjan ) 알고리즘입니다. 이 문제에서는 타잔 알고리즘을 사용해서 문제를 풀었습니다.강한 연결 요소와 타잔 알고리즘에 관한 내용은 여기에 정리해 두었습니다. [C++] 타잔( Tarjan )..

2024. 7. 14.