[알고리즘 스터디 솔루션] 17404, 10282, 13418

1. 17404 :: RGB거리 2

https://www.acmicpc.net/problem/17404

 

 

1) 풀이

해당 문제는 주어진 시간이 매우 적고, 현재의 최적해가 미래의 최적해의 부분이 아닐 수 있기에

다이나믹 프로그래밍 기법으로 풀어야 한다.

 

이전 집의 색을 고려하여

현재 집의 색을 고르는 방식으로

쉽게 풀이할 수 있다.

 

2) 주의할 점

첫 번째 집의 색을 계속 기억해야 하므로

2중 혹은 최대 3중 배열까지 고려해볼 수 있다.

 

3) 솔루션

#include <iostream>
#define INF 900'000'000
using namespace std;

int N;
int arr[1001][3];
int dp[1001][3][3];
enum COLOR { R, G, B, NONE };

int Solution(int idx, int preColor, int fstColor)
{
if (idx == N + 1)
return 0;

if (dp[idx][preColor][fstColor] != INF)
return dp[idx][preColor][fstColor];

int v = INF;
for (int i = 0; i < 3; i++)
{
if (preColor == i)
continue;

if (idx != N || (idx == N && i != preColor && i != fstColor))
v = min(v, Solution(idx + 1, i, fstColor) + arr[idx][i]);
}

return dp[idx][preColor][fstColor] = v;
}

int main()
{
cin >> N;

::fill(dp[0][0], dp[1001][3], INF);


for (int i = 1; i <= N; i++)
cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

int rst = INF;

for (int i = 0; i < 3; i++)
rst = min(rst, Solution(2, i, i) + arr[1][i]);

cout << rst;

return 0;
}

2. 10282 :: 해킹

https://www.acmicpc.net/problem/10282

 

1) 풀이

해당 문제는 단순 방향 그래프 문제이며, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 구하기 위해서는 마지막에 감염되는 컴퓨터까지의 시간기준 최단 거리를 구하면 된다.

 

다익스트라의 알고리즘을 적용하면 최단거리 배열이 나오는데

INF 값이 아닌 최대값이 해당 문제의 해이다.

 

2) 주의할 점

없음

 

3) 솔루션

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 999'999'999
using namespace std;

struct Node
{
bool operator<(const Node& other) const { return cst < other.cst; }
bool operator>(const Node& other) const { return cst > other.cst; }

int dst;
int cst;
};
vector<Node> adj[10001];

int T;
int N, D, C;

void Solution(int s)
{
vector<int> dist(N+1, INF);
dist[s] = 0;
priority_queue<Node, vector<Node>, greater<Node>> pq;
pq.push(Node{ s,0 });

while (!pq.empty())
{
auto peak = pq.top();
pq.pop();

for (auto it : adj[peak.dst])
{
int cost = dist[peak.dst] + it.cst;

if (cost < dist[it.dst])
{
pq.push(Node{ it.dst, cost });
dist[it.dst] = cost;
}
}
}

int cnt = ::count_if(dist.begin(), dist.end(), [](int a) {return a != INF; });
int maxv = -1;

for (auto it : dist)
if (it != INF)
maxv = max(maxv, it);

cout << cnt << ' ' << maxv << '\n';
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> T;

while (T--)
{
cin >> N >> D >> C;

for (int i = 0; i <= N; i++)
adj[i] = vector<Node>();

for (int i = 0; i < D; i++)
{
int a, b, c;
cin >> a >> b >> c;

adj[b].push_back(Node{ a,c });
}

Solution(C);
}

return 0;
}

 

 

3. 13418 :: 학교 탐방하기

https://www.acmicpc.net/problem/13418

 

1) 풀이

해당 문제는 최장 스패닝 트리와 최소 스패닝 트리를 구하는 문제이다.

간선의 수가 많기 때문에 O(Elog E) 크루스칼의 알고리즘보다는 프림의 알고리즘을 사용하는 것이

옳다.

 

해당 문제에서 최장 스패닝 트리를 구하기 위해서는 우선순위 큐를 최소힙으로 구현하면 된다.

(내리막길이 1이기 때문에 최소힙으로 구현해야함)

 

2) 주의할 점

없음

 

3) 솔루션

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

struct Node
{
bool operator<(const Node& n) const { return orm < n.orm; }
bool operator>(const Node& n) const { return orm > n.orm; }
int dst;
int orm;
};

vector<Node> adj[1001];

int N, M;

int BestSolution()
{
priority_queue <Node> pq;
vector<bool> visited(N + 1, false);
vector<Node> path;

pq.push(Node{ 0,-1 });

while (!pq.empty())
{
Node peak = pq.top();
pq.pop();

if (visited[peak.dst])
continue;

visited[peak.dst] = true;
path.push_back(peak);

for (auto it : adj[peak.dst])
pq.push(it);
}

int cnt = ::count_if(path.begin(), path.end(), [](const Node& n) {return n.orm == 0; });

return ::pow(cnt, 2);
}

int WorstSolution()
{
priority_queue <Node, vector<Node>, greater<Node>> pq;
vector<bool> visited(N + 1, false);
vector<Node> path;

pq.push(Node{ 0,-1 });

while (!pq.empty())
{
Node peak = pq.top();
pq.pop();

if (visited[peak.dst])
continue;

visited[peak.dst] = true;
path.push_back(peak);

for (auto it : adj[peak.dst])
pq.push(it);
}

int cnt = ::count_if(path.begin(), path.end(), [](const Node& n) {return n.orm == 0; });

return ::pow(cnt, 2);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> N >> M;

for (int i = 0; i <= M; i++)
{
int src, dst, orm;
cin >> src >> dst >> orm;

adj[src].push_back(Node{ dst,orm });
adj[dst].push_back(Node{ src,orm });
}

cout << WorstSolution() - BestSolution();

return 0;
}