[풀이] 트랩에는 연결된 간선이 역방향인 경우와 정방향인 경우 두가지 상태가 있습니다. 간선이 역방향이려면 트랩에 홀수번 방문한 상태여야 하며, 정방향인 경우는 방문을 안했거나 짝수번 방문한 상태입니다.
트랩의 개수가 최대 10개밖에 되지 않으므로 10개의 비트로 아래와 같이 트랩의 상태를 저장할 수 있습니다. 0000000000(0)~1111111111(2^10-1) (0인 경우 정방향, 1인 경우 역방향)
이를 이용해 vector<pair<int,int>> adj[1025][1001] 형태의 adj[state][node] 2차원 인접리스트를 선언한 뒤 state에 따라 올바른 간선 방향을 가지는 인접 리스트를 각각 만들어줍니다.
트랩의 개수가 k개라면 인접 리스트는 총 2^k개가 나올 수 있습니다. 만약 어떤 노드 u,v를 연결하는 간선이 입력으로 주어질 때, i) u,v가 모두 정방향인 경우(둘다 트랩이 아니거나, 트랩이어도 state 비트마스크에서 두 트랩 모두 0) u,v는 u->v 방향 그대로 저장
ii) u,v 둘중 하나가 트랩이면서 역방향인 경우 간선을 뒤집어야 하므로 v->u 방향으로 저장
iii) u,v 모두 트랩이면서 역방향인 경우 이 경우에는 간선이 u에 의해 한번 뒤집히고, v에 의해 또한번 뒤집히므로 결국 정방향인 상태가 됩니다. 그대로 u->v 방향으로 저장
위와 같이 state에 따라서 간선이 역방향, 정방향인지 정할 수 있고 각 state마다 인접 리스트(그래프)가 생성되게 됩니다.
이를 이용해 int dist[1025][1001] 배열을 선언하여 dist[state][node] : 현재 트랩의 상태가 state 일때, node까지의 최단 거리를 업데이트 해주는 BFS를 이용하여 end node까지의 거리를 구할 수 있습니다. 시간 제한이 10초로 넉넉하여 다익스트라를 사용하지 않고 일반 BFS를 사용하여도 AC를 받았습니다.
현재 노드가 cur 일때, 연결된 다음 노드 nxt가 트랩이라면 nxt에 연결된 간선이 뒤집어져야 하므로 state 비트를 변경해주어야 합니다. 간단히 bit xor 연산으로 다음 state를 구할 수 있습니다. 현재 state가 bit이고 nxt가 i번째 trap 이라면 next_bit = bit ^ (1<<i) 이 됩니다. i번째 bit만 뒤집어주면 되기 때문입니다.
다익스트라로 구현하면 end 노드에 처음 도착한 순간이 최단거리 이지만 BFS로 구현하였기 때문에 항상 최적의 경로로 방문하는 것이 아니어서 더이상 방문할 노드가 없을 때까지 계속 방문하며 최솟값을 업데이트 해주어야 합니다.
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
int dist[1025][1001];
bool trap[1001];
map<int,int> trapidx;
vector<pair<int,int>> adj[1025][1001];
bool isFlip(int a,vector<int>& flag){
return trap[a] && flag[trapidx[a]];
}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
for(int i=0;i<traps.size();i++) {
trap[traps[i]]=1;
trapidx[traps[i]]=i;
}
for(int i=0;i<(1<<traps.size());i++){
vector<int> flag(traps.size(),0);
for(int j=1;j<=n;j++) dist[i][j]=9e8;
for(int j=0;j<traps.size();j++) {
if(i&(1<<j)) flag[j]=1;
}
for(auto& r : roads){
int u=r[0],v=r[1],c=r[2];
int cnt = isFlip(u,flag)+isFlip(v,flag);
if(cnt==1) adj[i][v].push_back({u,c});
else adj[i][u].push_back({v,c});
}
}
queue<pair<int,int>> q;
dist[0][start]=0;
q.push({0,start});
int ans=9e8;
while(!q.empty()){
auto [bit,cur] = q.front(); q.pop();
if(cur==end) ans=min(ans,dist[bit][cur]);
for(auto [nxt,d] : adj[bit][cur]){
int nb = bit;
if(trap[nxt]) {
int i = trapidx[nxt];
nb ^= (1<<i);
}
if(dist[nb][nxt] > dist[bit][cur]+d){
dist[nb][nxt]=dist[bit][cur]+d;
q.push({nb,nxt});
}
}
}
return ans;
}
[풀이] 트리의 지름을 이용하여 해결하는 문제입니다. 트리의 지름이란 트리에서 가장 먼 두 점 a,b의 경로를 의미합니다. 임의의 점 x에서 가장 먼 점 y를 구하고 y에서 가장 먼 점 z를 구하면 y-z의 경로가 트리의 지름이 됩니다. ( https://blog.myungwoo.kr/112 블로그를 참고하시면 자세한 설명이 있습니다.)
문제의 주어진 트리에서 지름이 y-z1, y-z2 이렇게 두가지가 있다면 정답은 트리의 지름의 길이가 됩니다. 왜냐하면 세 점을 y , z1, z2 이렇게 정하면 z1-z2의 거리는 트리의 지름인 y-z1,y-z2보다 길어질 수 없기 때문에 y-z1의 길이가 무조건 중간값이 됩니다.
만약 트리의 지름이 y-z 한개밖에 나오지 않는다면 z에서 다시한번 트리의 지름을 구해봅니다. 만약 이때 위의 경우처럼 두가지가 나온다면 마찬가지로 트리의 지름의 길이가 중간값이 되고,
만약 이때도 한가지만 나온다면 (트리의 지름의 길이 -1)이 정답이 됩니다. 왜냐하면 트리의 지름이 단 한가지 경로만 존재하는 경우이며 이것보다 같거나 긴 경로는 없습니다. 그러므로 트리의 지름 y-z 에서 z와 인접한 점 w를 정해야 하는 나머지 한 점으로 설정하면 y-w-z 형태의 경로가 나오게 되고, y-z,y-w,w-z 중에 y-w가 (y-z의 길이 -1)로, 구해야 하는 중간값이 됩니다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[250001];
priority_queue<int> pq;
int mxD,from;
void dfs(int p,int m,int cnt,bool f){
if(mxD < cnt){
mxD=cnt;
from=m;
}
if(f && adj[m].size()==1) pq.push(cnt);
for(auto nxt : adj[m])
if(nxt!=p) dfs(m,nxt,cnt+1,f);
}
int solution(int n, vector<vector<int>> edges) {
for(auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
dfs(0,1,0,0);
int a = from; mxD=0;
dfs(0,a,0,1);
int t=pq.top(); pq.pop();
if(t==pq.top()) return t;
while(!pq.empty()) pq.pop();
a=from; mxD=0;
dfs(0,a,0,1);
t=pq.top(); pq.pop();
return t==pq.top() ? t : t-1;
}
[풀이] sales 배열의 크기가 최대 300000 이므로 판매원을 참석시킬 수 있는 모든 케이스를 다 해보기에는 시간이 너무 오래걸리기 때문에 다이나믹 프로그래밍을 사용해야 합니다.
우선 주어진 입력을 이용해 2차원 tree vector에 tree[parent].push_back(child) 와 같이 트리 형식으로 저장해줍니다.
Top-Down 방식을 이용하였고 sol(n)은 DP[n]은 구하고 return 합니다.
DP 배열은 아래와 같이 간단히 정의합니다. DP[n] : 루트가 n인 트리의 최소 비용.
루트가 n일때, 루트인 n 혹은 그 자식 노드중에 하나는 회의에 참석해야 합니다. 위의 케이스를 모두 계산해보고 그 중 최솟값을 DP[n]의 값으로 확정짓는 방식으로 DP[n]을 구합니다.
우선 풀이에 사용될 변수 v를 아래와 같이 정의합니다. v : n의 자식 노드가 nxt일 때 모든 DP[nxt]의 합 v = sum(DP[nxt])
점화식은 아래와 같습니다. DP[n] =
i) n을 회의에 참석 시킬 때, n을 참석 시킬 때 비용 sales[n]에 n의 자식 노드들의 최소비용을 더해주기만 하면 되므로 v + sales[n] 이 됩니다.
ii) n의 자식 중 하나인 nxt를 회의에 참석 시킬 때, root인 n은 참여하지 않았으므로 sales[n]은 더할 필요 없이 일단 v 값에 sales[nxt]를 더해줍니다. v값은 업데이트 되면 안되므로 임시변수 t를 선언하였습니다. t = v+sales[nxt]
여기서 v에 더해져 있던 sol(nxt) 값은 nxt가 회의에 참석 되는 것이 확정되었으므로 t에 빼주어야 합니다. 왜냐하면 sol(nxt)에는 nxt가 참여한 경우, 참여하지 않은 경우가 모두 포함되어 있기 때문입니다. t = v+sales[nxt]-sol(nxt)
여기까지 해주면 nxt의 자식들이 nnxt라고 했을 때, sol(nnxt)의 값도 빠져버려 nxt 자식 트리들의 비용은 반영이 안되어 버리기 때문에 sol(nnxt)의 값들은 다시 더해줘야 합니다. t = v+sales[nxt]-sol(nxt)+sum(sol(nnxt)) (nnxt는 nxt의 자식노드들) 위의 t 값이 nxt를 회의에 참여 시켰을 때의 최솟값이 됩니다.
만약 sol(n)에서 n의 자식이 없다면 회의에 참석할 필요가 없기 때문에 0을 return 합니다.
최종 DP[n]은 i),ii) 케이스 둘에서 나온 값들 중에 최솟값이 됩니다.
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
vector<int> sales,tree[300001];
int dp[300001],inf=1<<31-1;
int sol(int n){
if(tree[n].empty()) return 0;
int& ret = dp[n];
if(ret!=-1) return ret;
ret=inf;
int v=0;
for(int nxt : tree[n]) v+=sol(nxt);
ret=min(ret,v+sales[n-1]);
for(int nxt : tree[n]){
int t = v-sol(nxt);
t+=sales[nxt-1];
for(auto nnxt : tree[nxt]) {
if(!tree[nnxt].empty()) t+=sol(nnxt);
}
ret=min(ret,t);
}
return ret;
}
int solution(vector<int> _s, vector<vector<int>> links) {
sales = _s;
memset(dp,-1,sizeof(dp));
for(auto l : links) tree[l[0]].push_back(l[1]);
return sol(1);
}