11657. 타임머신 전형적인 벨만-포드 알고리즘 문제다. 음수 가중치가 있을 때, 한 점으로부터 다른 점들까지의 거리를 구한다. 음수 사이클을 판별할 때도 사용된다. 이 문제는 int를 사용할 경우 오버플로우가 발생해 출력 초과로 틀리게 되므로, long long 자료형을 사용해야 한다. #include #include #include #define UNREACHABLE LLONG_MAX using namespace std; struct Edge { int s; int e; int w; }; int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N ..
1197. 최소 스패닝 트리 최소 신장 트리(MST)를 구하는 기본적인 문제이다. MST는 머리, 손, 발, 몸통이 따로 있다고 할 때, 말 그대로 키(신장)가 가장 작도록 모든 노드를 연결하는 트리다. N개의 노드가 있을 때, MST의 간선 개수는 항상 N - 1이 된다. 유니온-파인드를 필수적으로 활용해 크루스칼 알고리즘을 이용한다. 가중치의 오름차순으로 정렬된 간선 리스트를 만든다. 연결된 간선 개수가 N - 1이 될때까지 반복한다. 간선 리스트에서 간선을 하나씩 꺼내, 대표 노드가 같지 않을 때(싸이클이 생기지 않을 때)만 union으로 대표 노드끼리 연결한다. #include #include #include #include #include using namespace std; int findRe..
Level 3. 부대복귀 전형적인 다익스트라 문제이다. 특정 지점에서 다른 지점까지의 최단 거리를 구할 때, 다익스트라를 사용한다. 이때 음수 가중치가 존재한다면, 벨만-포드를 사용한다. 벨만-포드는 음수 사이클을 확인할 때도 사용한다. 모든 지점 간의 최단 거리를 구할 때는 플로이드-워셜을 사용한다. 그 외에, 최소 신장 트리(MST)를 구할 때는 크루스칼을 사용한다. #include #include #include #define UNREACHABLE 200000 using namespace std; vector solution(int n, vector roads, vector sources, int destination) { vector answer; queue que; vector adj(n + 1..
1865. 웜홀 벨만-포드를 응용한 문제이다. 특정 지점에서 다른 지점까지의 최단 거리를 구할 때, 다익스트라를 사용한다. 이때 음수 가중치가 존재한다면, 벨만-포드를 사용한다. 벨만-포드는 음수 사이클을 확인할 때도 사용한다. 모든 지점 간의 최단 거리를 구할 때는 플로이드-워셜을 사용한다. 그 외에, 최소 신장 트리(MST)를 구할 때는 크루스칼을 사용한다. 이 문제는 벨만-포드 알고리즘을 수행해 1번부터 다른 지점까지의 최단 거리를 구한 후, 마지막 N번째에서 음수 사이클을 확인하는 문제다. 음수 사이클을 판별하는 것이 중점이므로, 몇 번을 출발지로 할 지는 중요하지 않다. 단, 1번에서 도달 불가능한 부분에 음수 사이클이 존재할 수도 있으므로, 이 문제에선 ∞를 확인하는 부분을 없애줘야 한다. #..
11003. 최솟값 찾기 우선순위 큐를 활용한 슬라이딩 윈도우 문제이다. 최소힙을 유지하는 우선순위 큐를 구성하고, 인덱스와 값을 넣는다. 매번 top에서 원소를 확인할 때, 유효 기간이 지난(인덱스를 벗어나는) 원소를 pop한 후 출력하면 된다. 현재 원소보다 큰 유효기간이 지난 원소는 어차피 효력이 없으므로 문제되지 않는다. #include #include using namespace std; struct Elem { int idx; int data; friend bool operator B.data; } }; int main(int argc, char* argv[]) { ios_base::sync_with_s..
Level 2. 이모티콘 할인행사 이모티콘의 개수가 다행이 7개 이하여서, 그냥 모든 할인율의 조합을 구해 풀라는 문제이다. 조합은 시작점과 레벨이 핵심인데, 이 문제에선 중복 조합이므로 레벨만 DFS 함수에 전달하면 된다. 이후, 이모티콘 플러수 가입자수를 키로 하고 최대 판매액을 값으로 하는 map을 만들어 계산하면 된다. #include #include #include #include using namespace std; void rDFS(int depth, vector& comb, vector& result) { if (comb.size()