프로그래밍

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

[난이도] Gold5
[유형] 다익스트라

[풀이]
다익스트라

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
int N,M,dist[50001];
vector<pair<int,int>> adj[50001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    for(int i=1;i<=N;i++) dist[i]=9e8;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,1});
    dist[1]=0;
    while(!pq.empty()){
        auto [d,cur] = pq.top(); pq.pop();
        if(dist[cur]!=d) continue;
        for(auto [nxt,nd] : adj[cur]){
            if(dist[nxt] > d+nd){
                dist[nxt]=d+nd;
                pq.push({dist[nxt],nxt});
            }
        }
    }
    printf("%d",dist[N]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/5972.cpp

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

[난이도] Gold2
[유형] 다익스트라

[풀이]
cost를 {쓰레기의 위치, 쓰레기에 인접한 위치}의 pair로 두고 다익스트라를 돌려주면 됩니다.

#include <cstdio>
#include <iostream>
#include <functional>
#include <queue>
#include <algorithm>
using namespace std;
struct P{
    pair<int,int> g,pos;
};
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},sy,sx,ey,ex;
char board[50][50];
pair<int,int> dist[50][50];
struct cmp{
    bool operator()(P& a,P b){
        if(a.g.first>b.g.first) return true;
        else if(a.g.first==b.g.first) return a.g.second>b.g.second;
        return false;
    }
};
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf(" %c",&board[i][j]);
            if(board[i][j]=='S') sy=i,sx=j;
            if(board[i][j]=='F') ey=i,ex=j;
            dist[i][j]={9e8,9e8};
        }
    priority_queue<P,vector<P>,cmp> pq;
    dist[sy][sx]={0,0};
    pq.push({{0,0},{sy,sx}});
    while(!pq.empty()){
        auto [g,pos] = pq.top(); pq.pop();
        auto [y,x] = pos;
        if(g!=dist[y][x]) continue;
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<0||nx<0||ny>=N||nx>=M) continue;
            pair<int,int> p = g;
            if(board[ny][nx]=='g') p = {g.first+1,g.second};
            else if(board[ny][nx]=='.') {
                bool ok=0;
                for(int j=0;j<4;j++){
                    int ty=ny+dy[j],tx=nx+dx[j];
                    if(ty<0||tx<0||ty>=N||nx>=M) continue;
                    if(board[ty][tx]=='g'){
                        ok=1;
                        break;
                    }
                }
                if(ok) p = {g.first,g.second+1};
            }
            if(p<dist[ny][nx]){
                dist[ny][nx]=p;
                pq.push({p,{ny,nx}});
            }
        }
    }
    printf("%d %d",dist[ey][ex].first,dist[ey][ex].second);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1445.cpp

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

[난이도] Gold2
[유형] 다익스트라

[풀이]
고객의 위치와 고객의 위치에서 상하좌우 인접 격자를 노드로 만든 뒤,
다익스트라를 돌리면 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <functional>
#include <queue>
using namespace std;
using ll = long long;
struct P{
    int u,v,d;
};
int N,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},id;
ll dist[800001];
vector<P> a[100001];
vector<pair<ll,int>> adj[800001];
bool inRange(int y,int x){
    return y>=0&&x>=0&&y<=100000&&x<=100000;
}
int main(){
    scanf("%d",&N);
    N++;
    for(int i=0;i<N;i++) {
        int y,x;
        scanf("%d%d",&y,&x);
        a[i].push_back({y,x,id++});
        if(i==0) continue;
        for(int k=0;k<4;k++){
            int ny=y+dy[k],nx=x+dx[k];
            if(inRange(ny,nx)) a[i].push_back({ny,nx,id++});
        }
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<a[i-1].size();j++){
            for(int k=0;k<a[i].size();k++){
                int d = abs(a[i-1][j].u-a[i][k].u)+abs(a[i-1][j].v-a[i][k].v);
                adj[a[i-1][j].d].push_back({a[i][k].d,d});
            }
        }
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,0});
    for(int i=0;i<id;i++) dist[i]=9e15;
    dist[0]=0;

    while(!pq.empty()){
        auto [d,cur] = pq.top(); pq.pop();
        if(dist[cur]!=d) continue;
        for(auto [nxt,cost] : adj[cur]){
            if(d+cost < dist[nxt]){
                dist[nxt]=d+cost;
                pq.push({dist[nxt],nxt});
            }
        }
    }
    ll ans=9e15;
    for(auto [u,v,id] : a[N-1]) ans=min(ans,dist[id]);
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/2159.cpp

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

[난이도] Gold2
[유형] 다익스트라

[풀이]
간선을 하나씩 제거해보며 다익스트라를 돌려보면 900ms 대로 아슬아슬하게 AC를 받을 수 있습니다.
최단거리에 포함된 간선만 제거해보는 방식으로 최적화를 하면 훨씬 빠른 시간내에 AC를 받을 수 있습니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;
int N,M,dist[1001];
vector<pair<int,int>> adj[1001],path;
int dijk(int a,int b){
    for(int i=1;i<=N;i++) dist[i]=9e8;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        auto [d,cur] = pq.top(); pq.pop();
        if(dist[cur]!=d) continue;
        for(auto [nxt,cost] : adj[cur]){
            if((cur==a&&nxt==b)||(cur==b&&nxt==b)){
                cost = 9e8;
            }
            if(dist[nxt]>d+cost){
                dist[nxt]=d+cost;
                pq.push({dist[nxt],nxt});
            }
        }
    }
    return dist[N];
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        adj[a].push_back({b,t});
        adj[b].push_back({a,t});
        path.push_back({a,b});
    }  
    int ans=0;
    for(auto [a,b] : path) ans=max(dijk(a,b),ans);
    if(ans>=9e8) {
        puts("-1");
        return 0;
    }
    printf("%d",ans-dijk(0,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/2307.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=582&sw_prbl_sbms_sn=16917

[난이도] level4
[유형] 다익스트라

[풀이]
1에서 출발해서 N까지 도착할때 필요한 최소 레벨을 구하는 문제입니다.
다익스트라를 응용해서 풀 수 있습니다.
일반적인 다익스트라의 경우 [현재 노드 cur 까지 올때까지 필요했던 cost] + [다음 노드 nxt까지 가는데 필요한 cost] 를 더해주어 이 값이 현재 dist[nxt]의 값보다 작다면 이 값으로 dist[nxt]를 업데이트 해주는 방식으로 풀지만
이 문제의 경우 [현재 노드 cur 까지 올때까지 필요한 최소 level]과 [다음 노드 nxt까지 가는데 필요한 level] 의
최댓값과 level[nxt]를 비교해서 업데이트 해주면 됩니다. 왜냐하면 nxt까지 가는데 둘중 더 높은 레벨만큼은 반드시 필요하기 때문입니다.

또한 문제의 조건에 따라 최종노드 N까지 가는데 필요한 level보다 크면서 가장 작은 소수를 구해야 하므로
level[N]보다 큰 첫번째 소수를 구해서 출력해주면 정답이 됩니다.

#include <cstdio>
#include <queue>
#include <functional>
#include <algorithm>
#include <cmath>
using namespace std;
int N,M;
int level[10001];
vector<pair<int,int>> adj[10001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=1;i<=N;i++) level[i]=1e9;
    pq.push({0,1});
    level[1]=0;

    while(!pq.empty()){
        auto [clv,cur] = pq.top(); pq.pop();
        if(clv!=level[cur]) continue;

        for(auto [nxt,lv] : adj[cur]){
            int nlv = max(lv,clv);
            if(nlv < level[nxt]){
                level[nxt]=nlv;
                pq.push({nlv,nxt});
            }
        }
    }
    for(int i=level[N]+1;;i++){
        bool ok=1;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0) {
                ok=0;
                break;
            }
        }
        if(ok) {
            printf("%lld",i);
            return 0;
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/지우는_소수를_좋아해.cpp

https://programmers.co.kr/learn/courses/30/lessons/81304

[난이도] level4
[유형] 비트마스크

[풀이]
트랩에는 연결된 간선이 역방향인 경우와 정방향인 경우 두가지 상태가 있습니다.
간선이 역방향이려면 트랩에 홀수번 방문한 상태여야 하며, 정방향인 경우는 방문을 안했거나
짝수번 방문한 상태입니다.

트랩의 개수가 최대 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;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/미로_탈출.cpp

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

[난이도] Gold3
[유형] 다익스트라

[풀이]
모든 집에 대해 다익스트라를 돌리면 시간초과가 나오기 때문에
모든 맥도날드와 cost 0으로 연결된 더미 노드, 모든 스타벅스와 cost 0으로 연결된 더미 노드를
추가 한 뒤, 각각 더미 노드에서 다익스트라를 돌리면
각 집에서 맥도날드 까지의 거리, 스타벅스 까지의 거리를 1차원 배열에 각각 저장할 수 있다.
이 두 배열을 가지고 조건 만족하는 최단 거리를 구해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
using ll = long long;
int V,E,M,X,Y;
vector<pair<int,int>> adj[10002];
ll dist[10002],md[10002],ans=1e12;
bool mac[10002],star[10002];
void dijk(int n){
    for(int i=0;i<=V+1;i++) dist[i]=1e12;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,n});
    dist[n]=0;
    while(!pq.empty()){
        auto qt = pq.top(); pq.pop();
        if(dist[qt.second] < qt.first) continue;
        for(auto p : adj[qt.second]){
            ll nxt = p.first;
            int cost = p.second;
            if(qt.first+cost<dist[nxt]){
                dist[nxt]=qt.first+cost;
                pq.push({qt.first+cost,nxt});
            }
        }
    }
}

int main(){
    scanf("%d%d",&V,&E);
    while(E--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    scanf("%d%d",&M,&X);
    while(M--){
        int v;
        scanf("%d",&v);
        mac[v]=1;
        adj[0].push_back({v,0});
    }
    scanf("%d%d",&M,&Y);
    while(M--){
        int v;
        scanf("%d",&v);
        star[v]=1;
        adj[V+1].push_back({v,0});
    }
    dijk(0);
    for(int i=0;i<=V+1;i++) md[i]=dist[i];
    dijk(V+1);

    for(int i=1;i<=V;i++){
        if(mac[i]||star[i]) continue;
        if(md[i]<=X&&dist[i]<=Y) ans = min(md[i]+dist[i],ans);
    }

    if(ans<1e12) printf("%lld",ans);
    else puts("-1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/13911.cpp

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

[난이도] Gold4
[유형] 다익스트라, 플로이드 워셜

[풀이]
원래 길이 있는 경우에는 비용이 안드므로 0의 cost,
단방향 통행만 가능하면 그 반대로 오는길은 1의 cost를 준 뒤
다익스트라를 돌려주면 몇개의 단방향 길을 바꿔야 하는지 알 수 있다.
모든 쿼리마다 다익스트라를 돌리면 시간초과가 나므로 출발점 N개에 대해
한번씩만 호출되도록 한다.

(플로이드 워셜로 풀면 훨씬 간결하게 풀 수 있다.)

#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
int N,M,K,inf=9e8;
vector<pair<int,int>> adj[251];
int s,e,dist[251][251];
void dijk(){
    fill(dist[s],dist[s]+N+1,inf);
    priority_queue<pair<int,int>> pq;
    dist[s][s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto qt = pq.top(); pq.pop();
        int cur = qt.second, cd=-qt.first;
        if(cd > dist[s][cur]) continue;
        for(auto next : adj[cur]){
            int nxt = next.first, nd = cd+next.second;
            if(dist[s][nxt] > nd){
                dist[s][nxt] = nd;
                pq.push({-nd,nxt});
            }
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,k;
        scanf("%d%d%d",&u,&v,&k);
        adj[u].push_back({v,0});
        adj[v].push_back({u,!k});
    }
    scanf("%d",&K);
    memset(dist,-1,sizeof(dist));
    while(K--){
        scanf("%d%d",&s,&e);
        if(dist[s][s]==-1) dijk();
        printf("%d\n",dist[s][e]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11562.cpp