다익스트라 덤벼랏!

Union Find를 조금 응용해볼까?

  • 문제

    방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

    입력

    첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

    출력

    첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

문제 아이디어

  • 정해진 출발점에서 다른 정점으로 가는 최단경로를 구하는 제일 기본적인 문제이다. 우리가 주의해서 봐야할 것은 아래 2가지이다.
    • 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있다
    • 경로가 존재하지 않는 경우 INF를 출력
  • 위의 2가지만 유의한다면 전에 포스팅한 다익스트라를 바탕으로 문제를 풀 수 있을 것이다.
  • 다익스트라 알고리즘의 제일 기본 문제이므로 아이디어는 필요하지 않다! 기본을 알고 있느냐 모르느냐가 이 문제의 관건!

문제 풀이

  • 나올 수 있는 거리의 최대치보다 높게 본인의 MAX 값을 설정해주어야 한다. 본인은 987654의 값으로 선언을 해주었다.
  • 인접행렬로 노드간의 표현을 하기보다는, 인접리스트를 사용해서 시간을 줄이는게 좋다. 본인은 adjMap을 이용하여 인접리스트를 생성하였다.
  • 방문 여부를 체크하고, 최종적으로 나타날 비용을 체크해주어야 한다. 그것을 위해 visitArr, costArr를 사용하였다.
  • 참 쉽죠>?

Code

오늘의 Tip!

Vector

  • vector<pair<int, int>> 에 대해서 우리는 항상 make_pair() 을 썼을 것이다. (나만 그런가?) 타자가 빠른 사람은 와다다닥 쓸 수 있겠지만, 타자가 느린 사람들에게는 저 11글자를 쓰는 것이 매우 곤혹스러운 일이다. 최대한 코드를 간결하고 ! 빠르게 쓰자는 마음으로 누구나 알고 있을 것 같은 매우아주작은 팁을 놓고 가겠다.

memset과 fill?

  • 우리는 배열 혹은 벡터를 선언하고 전체/부분 초기화를 해줄 때 for문을 이용하거나 memset과 fill을 사용할 것이다. 그러나 많은 사람들은 memset과 fill의 차이점에 대해서 알지 못한다! 그래서 우리는 그 차이점에 대해 알아보도록 할 것이다!

  • memset? 대부분 배열의 경우에는 0으로 초기화 하는 일이 많기 때문에 memset을 사용했을 것이다. 그러나 memset은 배열의 type 단위가 아니라 1바이트 단위로 초기화를 하기 떄문에 0으로 초기화를 할 때만 유효하다. 또한, 어셈블러로 작성이 되어 있어서 속도면에서는 무지 빠른 장점을 보여준다.

  • fill? 따라서 0이 아닌 값에 대해서 초기화를 해주기 위해서는 fill을 사용해야 한다. fill 메소드는 내부적으로 반복문을 수행하여 초기화를 해주기 떄문에 2차원 배열의 경우 for문으로 한번 더 초기화를 해주어야 한다.