2019-12-27

알고리즘 문제풀이 2019-12-27

boj 1753 - 최단경로

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

8미스…

틀려서 뭐가 문제인지 모르고 구현부분에 visit 체크가 원인인가 하고 계속 바꿔가면서 했는데 알고보니 start지정을 1번 정점으로 고정해놓고 하고 있었다…

그래도 삽질하면서 알고리즘의 원리는 좀더 이해한 것 같다.

신경쓸 부분이 두 가지 있다:

1. 거리 체크
2. visit체크

거리 체크의 경우

거리 체크에서 신경쓸 부분은 두 가지가 있다.

1. 우선 순위 큐 사용 거리 체크는 우선순위 큐를 쓰는게 편한데, 우선순위 큐에서 pair<int, int>를 쓸 경우 기본 comparator는 first를, 내림차순으로 꺼내게 된다. 그러므로 거리에 -를 붙여서 pair의 first로 넣으면, 따로 comparator 선언 없이 거리를 오름차순으로 정점들을 집어넣게 된다.

2. 어떤 거리를 집어넣는가. 다익스트라의 탐색은 결국 최단경로가 정해진 완료점들의 집합을 늘려나가는 식으로 수행하는데, 시작점에서 가장 가까운 순으로 찾아나가는 것이 중요하다. 그래서 우선순위 큐에 탐색점과 연결된 새 발견점을 집어넣을 때, 탐색점으로부터 그 발견점까지의 거리가 아니라, 시작점으로부터 그 발견점까지의 거리로 집어넣어야 한다.

여기에서 탐색점이 발견한 발견점까지의 거리가 갱신이 될 때만 그 발견점을 탐색점 큐에 넣으면 되는데, 이 문제에서는 거리가 갱신이 되지 않을 때에도 pair를 넣게 해도 시간초과는 나지 않는다. (150ms, 100ms 정도)

그냥 bfs로 모든 정점 늘려가면서 탐색하지 않고 다익스트라를 쓰는 이유는, bfs는 깊이만 고려하지 거리를 고려하지 않기 때문에 최단거리가 다른 순서로 탐색해야 찾아지는 경우도 있다는 점일 것이다.

visit 체크의 경우

1. 아예 없을 경우 큐에 정점을 계속 넣게 되어 메모리 초과/시간초과가 나게 되고,
2. 탐색점을 꺼내서 주변점을 체크하는 부분에 visit 체크를 넣으면 그 점을 다른 탐색점에서 찾아야 업데이트가 되는데 그런 경우가 무시되어 틀리게 된다.

발견점을 큐에 넣는 작업을 발견점까지의 거리가 새로 갱신될 때만 실행되도록 하면 무한 반복이 생기지 않고 잘 수행되는 것 같다. 그 부분이 if(dist+po.second<anss[po.first]){이 비교문이다.

cpp solution</summary>

const int LARGE=1e8+5;

vii adjs[20005]; // 인접 점까지의 거리를 담은 지그재그 리스트들의 배열
int anss[20005]; // 시작점 기준 특정 점까지의 거리를 담은 배열
bool visited[20005]; // 특정 점을 방문했는지의 여부

void solve(){
  int V,E;
  cin>>V>>E;
  int K;
  cin>>K;

  // 두 정점 사이에 여러 간선이 가능. 방향그래프.
  // 인접행렬? 인접리스트? 

  int t;
  int u,v,w;
  rep(V+1, t){
      adjs[t]=vii();
  }
  rep(V+5, t){
      anss[t]=LARGE;
  }
  rep(E, t){
      cin>>u>>v>>w;
      adjs[u].push_back({v,w});
  }
  // 플로이드의 알고리즘? : 모든점에서 모든점으로 찾는 알고리즘.
  // 여기서는: 한 시작점에서 다른 모든 점으로 거리를 찾아야 하므로, 다익스트라를 써야 할 듯
  // 다익스트라:
  // 모든 점을 무한으로 잡고, 시작점 0으로 시작하여,
  // 큐에서 발견점을 하나 꺼내 탐색 점으로 두고, 탐색점 주변의 미발견 점을 발견점 큐에 넣으면서 거리를 갱신한다.
  // 여기에서 priority queue를 쓰는 경우도 있다고 했는데, (거리 가까운 순?) 그건 어떻게 하는 지 잘 모르겠다.

  priority_queue<ii, vii> q;

  anss[K]=0;
  q.push({-0, -K});

  while(!q.empty()){
    ii p=q.top(); q.pop(); // 큐에서 탐색점을 하나 꺼낸다.
    int dist = -p.first; // 탐색점까지의 거리
    int no = -p.second; // 탐색점의 번호

    // 그럼 이제 탐색점 주변의 점들에 대해 순회한다.
    // 탐색점 주변의 점이 이미 발견된 점이면, 거리를 재 봐서 더 짧은 쪽을 쓰고,
    // 미발견 점이라면 (inf), 거리를 탐색점+탐색점-미발견 점 거리로 하되,
    // 그 점도 새로운 탐색점으로 탐색해야 하므로 큐에 넣는다.

    for(auto po : adjs[no]){ // po.first : 발견점의 번호, po.second : 탐색점으로부터 발견점까지의 거리
      // cout << po.first << ' ' << po.second << "search " << endl;
      if(dist+po.second<anss[po.first]){ // 시작점~탐색점 거리+탐색점~발견점 거리 < 발견점 거리, 즉 더 짧은 경로를 찾은 경우
        anss[po.first]=min(anss[po.first], dist+po.second);
        q.push({-anss[po.first], -po.first}); // 큐에 발견점을 넣는다.
      } else continue;
    }
  }

  for (int i = 1; i <= V; i++)
  {
    if(anss[i]>=LARGE) cout<< "INF\n";
    else cout << anss[i] << '\n';
  }
}

</details>