빵똥

https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 1. 접근 주어진 그래프를 위상 정렬을 하되 문제 속 조건인 Strahler의 순서를 구하는 조건을 참고하여 푸는 문제입니다. 입력의 간선 정보로 각 노드의 진입 차수를 저장하고 방문시마다 감소시키며 순서를 카운트하고 가장 큰 순서를 출력하면 되는데 기본 위상 정렬에서 조건을 조~~ 금 추가했다고 바로 오랫동안 삽질했습니다... 기본적으로 위상 정렬을 수행하는 코드에 스트롤러 순서를 정하는 부..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. 접근 문제 속 입력을 그래프로 만들어 위상 정렬하는 문제입니다. 처음에는 input으로 어떻게 그래프를 만들어야 하나 고민이 많았던 문젠데 예제 입력을 그림으로 그려보니 바로 이해가 되서 풀었던 문제입니다. 예제 입력의 두 번째 줄부터 간선 정보라 생각하고 그래프로 그려보면 다음과 같습니다. 입력 받은대로 단방향 그래프를 그리고 자신에게 향하는 간선이 없는 노드를 차례대로..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 접근 문제 속 요구사항은 일부 학생들의 키 비교 입력을 기준으로 전체 학생들을 줄 세우면 되는 문제입니다. 하단 알고리즘 분류를 보시면 알겠지만 그래프를 활용한 문제인데 직접적으로 그래프라고 알려주진 않습니다. 또한, 위 문제는 위상 정렬을 활용한 문제로 해당 알고리즘을 모르신다면 간단하게 보고 오시는 걸 추천드립니다! 앞서 그래프를 활용해야 한다고..