728x90 반응형 위상 정렬3 [백준] 1948번 : 임계경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서는 출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면서 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다. 단, 해당 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다. (에지 뒤집기 아이디어는 그래프 문제에서 종종 .. 2024. 3. 9. [백준] 1516번 : 게임 개발 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제를 해결하기 위해선 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다는 문장에 주목해야 한다. 각 건물을 노드라고 할 때, 그래프 형태에서 노드 순서를 정렬하는 위상 정렬 알고리즘을 사용하는 문제라는 것을 알아야 한다. 건물의 수가 최대 500, 시간 복잡도가 2초이므로 시간 제한 부담은 거의 없다. 입력 데이터를 바탕으로 필요한 자료구조를 초기화한다. 인접 리스트로 그래프를 표현하고 건물의 생산 시.. 2024. 3. 2. [백준] 2252번 : 줄 세우기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제이다. 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다. 위상 정렬(topology sort) : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 위상 정렬.. 2024. 2. 24. 이전 1 다음 728x90 반응형
