어흥

문제 링크: www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 1. 주의할 점 - 국왕의 현재 위치를 알고 있어야 한다 or 각 도로가 통제되는 시간을 알고 있어야 한다 - 조건에 맞게 구현을 정확히 해야한다 2. 구현 - 교차로의 수만큼 Dist[] 배열을 초기화한다 - 교황이 방문하는 교차로를 Loc 벡터에 담는다 - 모든 도로에 대한 정보를 V[] 벡터와 도로의 길이를 Road[][] 배열에 담는다 - rSum[] 배열에는 교황이 순서대로 방문하는 교차로까지 ..

문제 링크: www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 1. 주의할 점 - 세금이 오를때마다 다익스트라 알고리즘을 수행하지 않는다 2. 구현 - 기존 다익스트라 알고리즘에서 사용하던 Dist[] 배열을 변형시킨다 - Dist[][] 배열을 통해 [각 지점][각 지점까지 도달하는데 거친 Node수] 형태를 만족하며 최단경로 값을 저장한다 - dijkstra() 함수를 통해 Dist[..

문제 링크: www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 1. 주의할 점 - 다익스트라 혹은 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 간선에 대한 정보를 TC마다 초기화한다 - 간선에 대한 정보를 Arr[][] 배열에 입력받는다 - floydWarshall() 함수를 통해 각 노드사이의 최단거리를 구한다 - 친구들이 위치한 방을 V벡터에 받은 후, 1~Node번방까지 모두 모임의 방이라고 가정하며 모임방↔친구들이 위치한 방까지의..

문제 링크: www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - 최단경로를 구했을 때, 경로를 구하는 방법을 알고 있어야 한다 2. 구현 - 종종 나오는 다익스트라의 심화문제라고 할 수 있다 - Dist[] 배열을 통해 1번 Node부터 각 Node까지의 최단거리를 저장한다 - Pre[A] 배열을 통해 Dist[A]의 값이 갱신되었다면(최단거리로) 어떤 Node에서 왔는지 저장한다 - V[] 벡터를 통..

문제 링크: www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 1. 주의할 점 - 최단거리가 지름길을 안탈수도 있는 경우가 있다 2. 구현 - Dist[]를 통해 0부터 각 지점까지의 길이를 미리 저장한다 - 지름길에 대한 정보를 받을 때, 지름길의 도착지점이 목표지점을 넘어가거나, 사실상 지름길이 아닌 경우는 제외한다 - 0부터 도착지점까지 Dist[] 배열을 갱신하며, 만약 해당 지점에 지름길이 있는 경우, 지름길의 반대편까지의 거리를 기존 길이..

문제 링크: www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 플로이드 와샬 알고리즘(시간복잡도: O(N^3)로 50^3 < 10^9)을 사용하여 구한다 - 간선들의 정보를 입력 받기 전, Dist[][] 배열을 1000으로 초기화한다 - 간선들의 정보를 입력받은 후, 플로이드 와샬을 통해 IJ 까지의 최소 간선 수를 구한다 - 1~N번까지의 사람들 중에서 가장 먼 ..

문제 링크: www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 각 Node마다 보유한 아이템의 수를 Item[] 배열에 담는다 - 플로이드 와샬 알고리즘을 사용하기 위해 Arr[][] 배열을 미리 초기화한다 - 간선이 주어진 경우, Arr[][]에 대입한다 - 플로이드 와샬 알고리즘을 수행한 후, 각 지점마다 수색범위 D를 넘지 않을 경우, Temp에 해당 지역이 보유한 ..

문제 링크: www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 1. 주의할 점 - Dist[][] 배열을 항상 초기화한다 - 다익스트라 알고리즘을 통해 구하며, 길을 건너야 하는 경우를 1, 아닌 경우 0으로 놓고 푼다 2. 구현 - 입력받은 도로에 대한 정보를 Road[][][][]에 True 값으로 전환한다 - 소의 위치를 Cow 벡터에 저장한다 - 모든 소에 대해 우선순위 큐를 이용한 다익스트라 함수를 수행하여,..