4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1602 1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 문제에서 쿼리 형식으로 출발, 도착 노드에 대한 최소 시간을 묻고 있으므로, 모든 노드에 대해 다른 모든 노드까지의 최단경로를 구하는 플로이드-와샬 알고리즘이 적절할 것이다. 다만 도시 별 괴롭힘 시간이라는 별도의 가중치가 존재하는데, 멍멍이는 원숭이가 지나는 경로 중 가장 괴롭힘 시간이 긴 도시에서 괴롭히게 된다. 다만, 플로이드-와샬 알고리즘을..

문제 링크 : www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 문제를 그래프의 관점에서 이해하면 다음과 같다. ① 서로 연결된 사람은 같은 위원회에 참석한다 = 그래프에서 연결된 노드들은 같은 위원회(그룹)로 취급한다. ② 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. = 그래프의 모든 정점에 대해 그룹화한다. 즉 그래프의 모든 정점에 대해 연결된 노드끼리 그룹(위원회)으로 묶은 후, 그룹의 대표 노드에 대해 다른 모든 노드에 대한 전파 시..

문제 링크 : www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드-와샬 문제라는 것을 캐치하는 것이 문제 해결의 80%는 되는 것 같은 문제이다. 각 물건들의 무게 관계를 그래프의 형태로 이해하고, 문제에서 요구하는 것이 그래프의 각 노드에서 도달할 수 없는 노드들의 갯수이므로 모든 노드에서 다른 모든 노드로의 최단거리를 구하는 플로이드-와샬 알고리즘이 적절함을 캐치해야 한다. 플로이드-와샬 알고리즘(Floyd-Warshall ..

[최단거리 알고리즘] 다익스트라 알고리즘 (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층..

문제 링크 : www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 벨만-포드 알고리즘에 대한 전반적인 이해가 필요한 문제이다. 이 문제를 막힘없이 해결할 수 있다면 벨만-포드를 잘 이해했다고 볼 수 있을 것이다. 기본적으로는 (도로를 지나며 사용하는 비용 - 도시에 도착해서 벌 수 있는 비용) 을 간선의 비용으로 두는 그래프에 대해 벨만-포드 알고리즘을 적용해 문제를 풀면 된다. (즉 수익의 최대화는 가중치의 최소화가 된다.) 하지만 문제의 조건에서 gg는 오..

문제 링크 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 이해하고 연습해볼 수 있는 문제이다. 벨만-포드 알고리즘에 대해서는 다음 포스트를 참조하자. 벨만-포드 알고리즘(Bellman-Ford Algorithm) [서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘..

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

문제 링크 : www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라 알고리즘을 적용해 각 정점에 대한 K번째 최단경로의 가중치 합을 구하는 문제이다. 일반적인 다익스트라 알고리즘에서는 우선순위 큐(최소 힙)에서 pop되는 순간 그 정점에 대한 최소 가중치 합은 고정된다. (다익스트라 알고리즘 참조 : 4legs-study.tistory.com/21) 다익스트라 알고리즘은 기본적으로 최단거리를 구하..

문제 링크 : www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 어떠한 도시에 도착했을 때, 몇 개의 도로를 포장해서 이동했는지는 구별되어야 한다. 이전 포스팅인 BOJ16118_달빛 여우 문제처럼 가중치에 어떤 요소가 더해졌을 때는 이를 구별하기 위해 DP를 섞어 사용한다. 따라서, dist 배열을 dist[n][k]와 같은 이차원 배열 형태로 구성해 문제를 해결하자. dist[i][j] = i번 도시에 j개의 도로를 포장..