https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. Logic 우리가 이 문제에서 구해야 할 점은 2가지이다. 1. 모든 사람들이 만나는 시간. 2. 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수 : 도착점에 가장 늦게 도착하는 경로의 갯수 이제 구하는 로직을 설명해 볼건데 순서대로 보면 1. 모든 사람들이 만나는 시간. 모든 사람들이 만나려면 도착점에 먼저 들어온 사람은 가장 늦게 도착한 사람이 올 때 ..
위상정렬
https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. Logic 각 PD들이 뽑은 가수의 순서대로 공연순서를 정하는 것이기 때문에 순서를 정할 때 사용하는 위상 정렬을 사용할 수 있다. 처음 입력을 받을 때만 잘 받아주면 어려움 없이 풀 수 있다. 테스트케이스를 예시로 보면 1 > 4 > 3 순서대로 받아줘야 하기때문에 1 > 4 4 > 3 끊어서 입력받아줘야 한다. 2. Code #include using namespace..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. Logic 이 문제를 풀 때 중요한 키포인트는 두 가지 이다. 1. 1번 건물의 건설이 완료되어야만 2번과 3번 건물의 건설을 시작할 수 있다. 2. 2번과 3번의 건설을 동시에 진행 될 수 있다. 1번 건물의 건설이 다 끝나고 2번과 3번 건물을 건설하지만 3번 건물을 지을동안 2번 건물이 완성되더라도 아직 3번 건물이 다 안지어졌기 때문에 4번 건물을 짓지 못한다. 이 말은 항상 최..
1. 위상정렬이란? 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법. 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다. 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 / Edge : 간선의 갯수} 2. Default Logic 위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다. 먼저 BFS를 사용한 방법을 말로 설명해 보자면 1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수) 2. 한 간선을 처리한 후 inDegree를..
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. Logic 2252번 문제와 동일하게 위상정렬로 푸는 문제지만 살짝 다르다. 1766번 문제집은 문제를 푸는 조건이 있다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 이중 키포인트는 3번이다. 나는 위상정렬을 BFS를 활용하여 푸는데 1..
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. Logic 대표적인 위상정렬 문제 위상정렬이란? 비순환 방향 그래프(DAG: Directed Acyclic Graph)에서 정점을 선형으로 정렬하는 것. 만약 그래프가 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선(u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 나는 BFS를 사용하는 방식으로 풀이했다...
