4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제의 조건을 잘 살펴보자. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 제시된 조건들을 봤을 때 문제집의 문제 간에는 선행 관계가 존재함을 알 수 있으며, 따라서 이 문제는 사이클이 없는 방향 그래프 내에서 위상 정렬의 결과를 출력하는 문제임..

위상 정렬 (Topological Sort) 방탈출 게임을 한다고 생각해 보자. 우리는 메인 룸에 있는 3개의 자물쇠를 풀어야 탈출에 성공하고, 다음 단계의 탈출에 도전할 수 있다. 3개의 열쇠는 메인 룸과 연결된 3개의 방에 각각 하나씩 숨겨져 있다. 따라서, 메인 룸에서 나가기 위해서는 방 A, B, C 에서 열쇠를 모두 찾아야만 할 것이다. 단 열쇠를 찾는 순서는 영향을 주지 않는다. 또한 열쇠를 3개 모두 찾지 못하면, 다음 단계의 탈출에는 도전할 수 없을 것이다. 따라서 다음 단계의 탈출에 도전하기 위해서는 다음과 같은 순서를 따라야 한다. (A방에서 열쇠를 찾음 - B방에서 열쇠를 찾음 - C방에서 열쇠를 찾음) - 메인 룸의 자물쇠를 모두 푼다 - 메인 룸에서 탈출 후 다음 단계에 도전 (A..

[서론] 그래프 최단경로 알고리즘으로, 꽤 자주 보이는 유형이다. 다익스트라 알고리즘은 음수가 아닌 가중치가 있는 그래프에서 한 점으로부터 다른 모든 점까지의 최단 경로를 구하는 알고리즘이다. [동작 원리] 다음과 같은 그래프에서, 1번 노드와 나머지 각 노드 간의 최단거리를 다익스트라 알고리즘을 통해 구해보자. 다익스트라 알고리즘은 위와 같은 상태에서 시작한다. 테이블의 값은 출발 노드로부터 해당 노드까지의 최소 가중치 합을 의미하며, 테이블의 값이 INF(무한대)라면 해당 노드와 연결되어 있지 않다는 의미이다. 아직은 1번 노드만 확인했으므로, 다른 모든 노드에 대해 INF가 기록된 모습이다. 출발 노드로부터 인접한 각 노드에 대해 테이블에 거리를 기록한다. 예시 그래프에서는 출발 노드 1이 2, 3..