[백준] No.1162 - 도로포장 (C++, 다익스트라)

문제

 

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

1162번: 도로포장

 

풀이

 

solved.ac 난이도: Gold 1

 

다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제.

단순히 모든 도로들 중 K개의 도로들을 선택하여 cost를 0으로 만든다면,

모든 조합의 최대 수는 Combination(50000 , 20) 일 것이다.

이는 절대 시간안에 계산해낼 수 있는 수치가 아니다.

 

따라서 다익스트라를 진행하면서 방문하게 되는 간선(도로)을 포장할지 포장하지 않을지 선택하자.

이때의 최단 거리는 2차원 배열 dist[도시의 번호][포장된 도로 수]에 저장한다.

dist[city_idx][paved] = 1번 도시에서 city_idx번 도시까지의 도로 중에 paved개를 포장한 최단 거리.

 

해당 도로를 포장한다면 paved +1 이 K보다 작은지 확인해주고

dist[next_city][paved+1]의 최단 거리에 접근해주면 된다.

 

struct Distance{
  ll cost;
  ll idx;
  ll paved;
 
  bool operator<(const Distance& a) const{
    return cost > a.cost;
  }
};
 
int city_num, road_num, pave_num;
vector<pair<ll,ll>> adj[10001];
 
ll Dijkstra(int start_node){
  ll dist[10001][21];
  memset(dist, 0x3f, sizeof(dist));
 
  priority_queue<Distance> pq;
  pq.push({0,start_node,0});
  dist[start_node][0] = 0;
 
  ll now_node, next_node, paved;
  ll cost, next_cost;
 
  while(!pq.empty()){
    now_node = pq.top().idx;
    cost = pq.top().cost;
    paved = pq.top().paved;
    pq.pop();
 
    if(dist[now_node][paved] < cost)
      continue;
 
    for(int i=0; i<adj[now_node].size() ; ++i){
      next_node = adj[now_node][i].second;
      next_cost = cost + adj[now_node][i].first;
 
      if(next_cost < dist[next_node][paved]){ //포장하지 않는 경우
        pq.push({next_cost, next_node ,paved});
        dist[next_node][paved] = next_cost;
      }
 
      if(paved  < pave_num && cost < dist[next_node][paved+1]){ //포장하는 
        pq.push({cost, next_node ,paved+1});
        dist[next_node][paved+1] = cost;
      }
    }
 
  }
 
  ll min_cost = MAXTIME;
  for(int i=0; i<=pave_num ; ++i)
    min_cost = min(min_cost, dist[city_num][i]);
 
  return min_cost;
}
 

 

 

추가적인 내용(memset에 대하여)

 

이번 문제에서 맞게 해결했다고 생각했는데 시간초과가 계속 발생하여 모든 요소를 최적화해보면서 알게 된 memset 함수에 대해 좀 더 알아보자.

 

다익스트라 문제를 풀때 dist의 초기값을 0x3f로선언하는 경우가 많다.

memset(dist, 0x3f ,sizeof(dist));

그 이유는 memset함수는 바이트 단위로 주소 값을 초기화해 주기 때문이다.

주로 많이 사용되는 -1은 보수 표현법에 의해 모든 비트 값이 1로 설정된다.

11111111  11111111  11111111  11111111

이중에 어떤 바이트를 선택하더라도 모두 11111111의 값을 동일하게 갖는다.

 

0x3f의 경우 1바이트의 이진수로 표현하면 다음과 같다.

0011 1111

 

따라서 int형의 배열이든 long long형의 배열이든 모든 바이트가 0011 1111로 설정된다.

ex) int형 배열:  0011 1111 0011 1111 0011 1111 0011 1111

이는 각 변수형의 최댓값을 나타내진 못하더라도 거의 근접한 값을 갖는다.

특히 signed형의 변수형은 맨 앞의 비트로 값의 부호를 나타내므로 이를 고려하여 더 큰 값으로 초기화를 해주고 싶다면

0x7f = 0111 1111

을 초기화 값으로 이용해 주자.

 

 

참조 블로그: chogahui05님의 "memset : 배열 초기화 할 때 많이 쓴다." 게시글

 

 

 

사실 시간 초과는 구조체의 operator<의 구현이 잘못된 것이 원인이었다...

 

 

 

참조 풀이: JusticeHui님의 게시글

코드