문제 풀이/백준 (BOJ)

[백준/BOJ] 1516번: 게임 개발 ( 위상 정렬 사용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1516 풀이이 문제는 건물 건설에 걸리는 시간을 출력하는 문제입니다.그런데, 이 건설 시간은 한 건물을 건설하는데 사전에 필요한 건물들의 건설 시간을 모두 포함한 시간입니다. 이러한 문제를 푸는 데, 위상 정렬( topology sort ) 알고리즘이 적합합니다.위상 정렬은 어떤 과제를 해결하는데 먼저 수행해야 되는 작업을 나열하는 알고리즘입니다. 위상 정렬에 관한 내용은 여기에서 볼 수 있습니다. [C++] 위상 정렬( Topology Sort )위상 정렬( Topology Sort )이란위상 정렬이란 주어진 DAG( Directed Acyclic Graph )에서 간선의 방향에 따라 모든 정점을 나열하는 것을 말합니다...

2024. 8. 14.
문제 풀이/백준 (BOJ)

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

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

2024. 7. 17.
문제 풀이/백준 (BOJ)

[백준/BOJ] 1766번: 문제집 ( 위상 정렬 ) - C++ 문제 풀이

문제 풀이 문제 링크: https://www.acmicpc.net/problem/1766 풀이이 문제는 문제집의 문제들을 푸는 우선순위에 따라 문제 번호를 나열하는 문제입니다. 이 문제처럼, 선행 과제의 해결이 필수적인 경우이며, 주어진 과제 간의 선행 관계가 비순환적이라면, 위상 정렬 방법으로 문제를 해결할 수 있습니다. 위상 정렬이란 비순환 방향 그래프( DAG )가 주어질 때, 그래프의 정점들을 간선의 방향에 따라 나열하는 알고리즘입니다. 좀 더 자세한 정보는 여기에서 볼 수 있습니다. [C++] 위상 정렬( Topology Sort )위상 정렬( Topology Sort )이란위상 정렬이란 주어진 DAG( Directed Acyclic Graph )에서 간선의 방향에 따라 모든 정점을 나열하는 것..

2024. 7. 14.
문제 풀이/백준 (BOJ)

[백준/BOJ] 2252번: 줄 세우기( 위상 정렬, Topology Sort ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2252 풀이이 문제는 학생들의 키를 비교하여 학생들을 나열한 결과를 출력하는 문제입니다. 이 문제는 두 학생 간의 키 비교 결과를 알려줍니다.한 학생이 다른 학생 앞에 서야 한다는 정보입니다.이 정보를 통해서 학생들 간의 위치 관계를 알 수 있고, 추상적으로 방향 그래프를 구성할 수 있습니다.그리고, 그 그래프는 당연히 순환 경로가 존재하지 않음을 알 수 있습니다.( A라는 학생이 B 학생보다 작으면, B 보다 큰 학생 C보다 클 수는 없습니다. ) 이러한 문제는 위상 정렬 알고리즘을 사용해 해결할 수 있습니다. 위상 정렬이란 비순환 방향 그래프( DAG )가 주어질 때, 그래프의 정점들을 간선의 방향에 따라 나열하는 알고..

2024. 7. 14.
알고리즘

[C++] 위상 정렬( Topology Sort )

위상 정렬( Topology Sort )이란위상 정렬이란 주어진 DAG( Directed Acyclic Graph )에서 간선의 방향에 따라 모든 정점을 나열하는 것을 말합니다.여기서, DAG란 순환 경로가 없는 방향 그래프를 말합니다. 그리고, 간선의 방향을 따른다는 뜻은,정점 A에서 B로 이어지는 간선이 있을 때, A가 B보다 먼저 나열되어야 한다는 뜻입니다. 예를 들어, 다음 그래프는 DAG입니다.  이때, 위상 정렬을 하면 3, 1, 2가 됩니다. 이렇게 정점들을 나열하는 것은, 작업들 중에서 먼저 수행해야 되는 작업 순으로 작업들을 나열하는 과정과 같습니다.그래서, 위상 정렬은 순환 경로가 있는 그래프에서는 성립되지 않습니다.먼저 나열해야 하는 정점을 지정할 수 없기 때문입니다.    이러한 위..

2024. 7. 12.