4Legs_Archives

문제 링크 : www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 간선들은 그 간선의 양 끝 노드에 불이 옮겨진 순간부터 타는 시간이 절반으로 줄어들게 된다. 쉽게 설명하자면 다음 그림과 같다. 정점 A에 불이 먼저 붙은 상황이다. 이 때, A와 B를 잇는 간선은 A쪽에서 먼저 타게 된다. B쪽에는 아직 불이 도착하지 않았기 때문이다. 이제 정점 B에도 불이 붙었다. 이제는 간선의 남은 길이가 양쪽에서 타..

문제 링크 : 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/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 그래프의 단절점이란, 그래프에서 한 정점을 제거했을 때 그래프의 Connected Component가 증가하는 정점을 말한다. Connected Component는 DFS, BFS 등으로 그래프를 탐색했을 때 한 덩어리로 묶이는 정점들의 집합이라 이해하면 된다. 즉 그래프의 모든 정점을 발견하는 데 실행되는 탐색의 횟수와도 같다. 다음 그래프를 통해 단절점의 특징을 파..

문제 링크 : www.acmicpc.net/problem/15562 15562번: 네트워크 우리의 회사에는 N개의 네트워크 시스템 S1, S2, ..., SN와 이들을 연결하는 M개의 네트워크들 W1, W2, ..., WM이 있다. 네트워크 시스템들은 우선순위가 있어 모든 네트워크는 우선순위가 www.acmicpc.net 임의의 시스템 K에 대해 다음과 같은 경우를 생각해보자. 이 경우, 문제의 조건에 따라 네트워크를 정리하면 다음과 같다. 만약 K에서 B ~ F로 각각 나가는 간선이 하나씩 존재하더라도, 이 간선들은 모두 A에서 B ~ F로 나가는 간선으로 대체될 수 있다. 즉, 한 노드를 기준으로 자신에게 들어오는 간선이 존재한다면, 자신에게서 나가는 간선들은 위의 A -> B와 같이 대체될 수 있다..

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

[최단거리 알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) [서론] 최단거리 알고리즘의 마지막, 플로이드-와샬 알고리즘(이하 플로이드 알고리즘)이다. 플로이드 알고리즘은 그래프에서 모든 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 그래서 이전까지의 최단거리 알고리즘과는 다르게 dist배열이 처음부터 2차원 배열 형태이다. 벨만-포드 알고리즘과 마찬가지로 음의 가중치가 존재하는 그래프에서도 사용 가능하며, 음의 사이클이 존재하는 경우 최단거리를 구할 수 없다. [동작 원리] 플로이드 알고리즘은 출발 노드, 도착 노드 그리고 중간 노드를 통해 DP와 유사하게 동작한다. 편의상 이들을 From, To, Mid..

문제 링크 : www.acmicpc.net/problem/2593 2593번: 엘리베이터 첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 Xi와 Yi가 빈 칸을 사이에 두고 주어지며, 마지막 줄에는 A와 B가 주어진다. N은 100,000이하, M www.acmicpc.net 문제를 그래프의 관점에서 이해하는 것이 중요한 문제이다. 문제에서 층은 최대 10만개, 엘리베이터의 갯수는 최대 100개이므로 BFS를 적용할 때 층이 아닌 엘리베이터를 기준으로 해야 함을 캐치할 수 있다. (BFS의 시간복잡도는 일반적으로 O(V^2)이다.) 문제에서 제시된 예제를 통해 설명하자면, 아래와 같은 엘리베이터 상황을 4층에서 7층으로 이동 가능, 7층에서 12층..

[서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘 : 4legs-study.tistory.com/21) 하지만, 다익스트라 알고리즘에는 그래프에 음의 가중치가 없어야 한다는 조건이 있었다. 왜일까? 음의 가중치를 가진 간선이 존재한다면, 힙에서 한 정점을 꺼냈을 때 그 가중치 합이 해당 정점에 대한 최소 가중치 합임을 보장할 수 없기 때문이다. 다익스트라 알고리즘은 힙에서 꺼낸 정점에 대해 꺼낸 순간의 가중치 합을 최소로 고정한 후 (음의 가중치가 없다면 다른 어떤 간선을 추가로 지나오더라도 현재 가중치 합보다 작아질 수 없으므로) 다른 정점에 대해 해당 과정을 반복하는데, 음의 가중치를 가진..

문제 링크 : www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 결국 문제는 특정한 하나의 간선을 출발지로부터의 최단경로에 포함하는 노드들을 구하는 것이다. 후술할 다른 풀이방법도 있지만, 문제의 의도에 따라 다익스트라 알고리즘을 적용해 정석으로 풀이해보자. 위의 예제 그래프에서 2번 노드에서 어떤 목적지 후보 노드에 대한 최단경로가 1-3 간선을 포함하고 있다면, 1번 노드에서 그 목적지 후보 노드에 대한 최단거리는 출발 노드로부터 목적지 후보 노드까지..