도로포장 (BOJ 1162)

문제

이미지 클릭

문제 설명

• 준영이는 서울(1번 도시)에서 포천(n번째 도시)으로 이동함.
• m개의 도로가 존재하고 k개의 도로의 이동시간을 0으로 만들 수 있음.

문제 해설

이 문제는 다익스트라와 dp를 주요하게 활용한다면 쉽게 풀 수 있는 문제이다.

1. 다익스트라: 기본적으로 최단거리를 탐색하는 데 사용.
2. 다이내믹 프로그래밍: k개의 도로의 이동시간을 0으로 만드는 경우의 최소 시간을 체크해 줌.

최종 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
struct P {
  ll a, b, c;
  bool operator>(const P &other) const { return a > other.a; }
};
int n,m,k;
const ll inf = 1e18+4;
vector<pair<int,int>> v[50004];
ll visited[10004][24];
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>m>>k;
  for(int i=1,x,y,z;i<=m;i++){
    cin>>x>>y>>z;
    v[x].push_back({y,z});
    v[y].push_back({x,z});
  }
  fill(&visited[0][0],&visited[0][0]+10004*24,inf);
  priority_queue<P,vector<P>,greater<P>> q;
  q.push({0,1,0});
  visited[1][0]=1;
  while(q.size()){
    ll x = q.top().b,y=q.top().a,cnt=q.top().c;
    q.pop();
    if(x==n) continue;
    if(visited[x][cnt]<y) continue;
    for(auto i:v[x]){
      ll xx=i.first,yy=i.second;
      if(visited[xx][cnt]>yy+y){
        visited[xx][cnt]=y+yy;
        q.push({yy+y,xx,cnt});
      }
      if(cnt<k){
        if(visited[xx][cnt+1]>y){
          visited[xx][cnt+1]=y;
          q.push({y,xx,cnt+1});
        }
      }
    }
  }
  ll mn=inf;
  for(int i=0;i<=k;i++) mn=min(mn,visited[n][i]);
  cout<<mn;
}

 

차근차근 살펴본다면 다음과 같이 구분하여 코드를 이해할 수 있다.

 

-큐에 넣는 값 & 초기화

struct P {
  ll a, b, c;
  bool operator>(const P &other) const { return a > other.a; }
};
priority_queue<P,vector<P>,greater<P>> q;
q.push({0,1,0});
visited[1][0]=1;

 

queue에는 순서대로 이동 시간, 현제 위치, 이동 시간을 0으로 만든 횟수를 넣어준다. 그리고 visited [n][k]는 n번째 위치에서 k번의 이동 시간을 0으로 초기화하였을 때 이동 시간을 의미한다.

 

-최단 거리 구하기

 while(q.size()){
    ll x = q.top().b,y=q.top().a,cnt=q.top().c;
    q.pop();
    if(x==n) continue;
    if(visited[x][cnt]<y) continue;
    for(auto i:v[x]){
      ll xx=i.first,yy=i.second;
      if(visited[xx][cnt]>yy+y){ //1
        visited[xx][cnt]=y+yy;
        q.push({yy+y,xx,cnt});
      }
      if(cnt<k){
        if(visited[xx][cnt+1]>y){ //2
          visited[xx][cnt+1]=y;
          q.push({y,xx,cnt+1});
        }
      }
    }
  }

 

기본적인 조건

• x(현제 위치)가 n인 경우에는 continue
• 내가 방문할 위치의 이동거리가 현제 내가 이동한 거리보다 작다면 continue

for문 내부

• 도로의 이동시간을 0으로 하지 않고 이동하는 경우 확인하기... 1번 경우
• 만약 cnt(지금 까지 도로의 이동 시간을 0으로 한 횟수)가 k보다 작은 경우에는 도보의 이동시간을 0으로 하고 이동하는 경우도 확인해 주기... 2번 경우

이미지 클릭