4Legs_Archives

문제 링크 : www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 순위의 개념을 그래프에 위상 정렬을 적용하여 나타낼 수 있는가를 묻는 문제이다. 다만 초반 그래프를 구성하는 것이 다소 까다롭다. 위상 정렬 (Topological Sort) 위상 정렬 (Topological Sort) 방탈출 게임을 한다고 생각해 보자. 우리는 메인 룸에 있는 3개의 자물쇠를 풀어야 탈출에 성공하고, 다음 단계의 탈출에 도전할 수 있다. 3개의 열쇠는 메인 룸과 연 4le..

문제 링크 : www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 k www.acmicpc.net 문제에서 주어진 레시피는, 한 물약을 만들기 위해 필요한 물약에 대한 정보이다. 즉, 레시피의 왼쪽에 있는 물약들을 모두 가지고 있어야 오른쪽의 물약을 만들 수 있다. 이는 곧 하나의 물약을 만들기 위해서는 다른 물약의 제조가 선행되어야 함을 의미하며, 따라서 이 문제를 위상 정렬 문제로 접근할 수 있다. 위상 정렬 (Topological Sort) 위상 정렬..

문제 링크 : 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..