3. 알고리즘 정리 [최단 경로]

최단 경로에 대한 알고리즘을 정리해보자.

엇 최단 경로면 BFS 아닌가?

응 아니야~ 그러면 시작해보자

 

특정 시작노드에서부터  가중치를 더해가면서 계산하는 다익스트라 알고리즘이라는 것을 써야한다.

다익스트라 알고리즘이란?

BFS랑 유사하지만 조금 다른 개념이다.

BFS는 단순 가장가까운 노드부터 계산해서 큐에 넣고 빼서 체크를 했다면

다익스트라는 가까운 노드만 업데이트를 하는것이다.

 

그래서, 우선순위 큐는 minHeap방식을 활용해서 가장 짧은 거리를 가진 노드 정보만 꺼내고 업데이트한다.

 

좀더 자세히 알아보자

 

* 최단 경로

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

1753번: 최단경로

 

일단, 최단 경로에 대한 개념은 이렇게 이다.

 

1. 입력 받는것들 다 처리 2차원 배열에 값을 넣고,

2. 중요한 변수 선언 = 총 노드 연결 및 가중치 값을 담는 배열 / 총 최단 거리 최종 본 배열 /  방문했는지 체크 배열

3. 만약에, 최종 거리 배열값이 이전 거리 + 신규 거리보다 크다면, 최종 거리 배열을

신규 거리 합친걸로 update해준다

 

이게 무슨 말이냐면, 예를 들어서 1 -> 3으로갈때 가중치가 5라고 가정해보자

1 ->2 로갈때 1 , 2->3으로 갈때 1이면, 합이 2 가되고, 이건 이전 최종 배열 에 있던 값보다 작게되어

더 최단 거리이게 된다.

따라서 해당 값으로 update를 해준다. 

이렇게 체크체크를 해서 최종으로 나온 최종 거리 배열을 return 해주면된다.

 

그러면 코드를 보자, 

처음에 삽질했던 배열을 사용한 코드를 먼저 올려보겠다. 

 

1) 배열 사용 (백준에서는 이방법으로 하면, 메모리초과 오류남, 노드의 개수가 커서)

 

우선 총 2차원 배열에, 넘어오는 가중치 값을 넣어준다.

예를 들면, 2->1로 가는 가중치가 3이라고 하면, adj[2][1] =3 이런식으로 다 넣어준다.

그리고, 최소 값을 항상 가지고있어야 하기 때문에, 우선, 최종 거리 배열은 int의 최대값으로 가지고있는다.

 

해당 하위의 부분은 어떤거냐면, 현재 연결 된 값들 중, 방문하지않았고, 가장 최소 비용을 가지고있는 값의 index를 반환하는 것이다. 예를 들면 1이랑 연결된 노드가 2,3,4 라고 하면 1 -> 2 가중치가 3  1->3 가중치가 5, 1->4 가중치가 4

이렇게 되면, 다음에 탐색할 노드는 가중치가 제일 적은 2를 다음 index로 탐색하시오 이다. 그렇게 되면

다음 2랑 연결된 애가 선상에 오르고, 이제 본 최단거리 알고리즘이 돌기 시작한다.

 

여기가 해당 알고리즘의 핵심 소스이다.

방문한적이없는데, 만약에 해당 다음 노드에서 특정 노드로의 거리가 0이아닌경우, 즉 1->3과 1->2->3 이 두가지 경우가 모두 존재하는 경우에 해당 거리를 비교한다. 1->3 보다 1->2->3 이 더작은지

작다면 update한다.

 

이렇게 몇번 돌면, 완성이되는데

중요한건 간선이 많은 경우에 이런 코드방식은 메모리 초과가 난다.

(전체 코드)

import java.util.*;

public class Main
{
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int nodeCount = sc.nextInt()+1;
       int connCount = sc.nextInt();
       int startnode = sc.nextInt();
       int [][] adj = new int[nodeCount][nodeCount];
       
       for(int i =0;i<connCount;i++)
       {
           adj[sc.nextInt()][sc.nextInt()] = sc.nextInt();
       }
       int [] distance = new int[nodeCount];
       boolean [] checked = new boolean[nodeCount];
       Arrays.fill(distance,Integer.MAX_VALUE);
       
       distance[startnode] = 0;
       
       for(int i =1;i<nodeCount;i++)
       {
           int min = Integer.MAX_VALUE;
           int index = -1;
           for(int j =0;j<nodeCount;j++)
           {
               if(!checked[j] && min > distance[j])
               {
                   index = j;
                   min = distance[j];
               }
           }
           if(index == -1)
           {
               break;
           }
           // -- 여기까지 하게 되면,연결 된 노드 중, 가장 가중치가 작은 노드가
           //다음 노드로 선택
          for(int j =0;j<nodeCount;j++)
          {
              if(!checked[j] && adj[index][j] != 0 && distance[index] != Integer.MAX_VALUE
              && distance[index] + adj[index][j] < distance[j] )
              {
                  distance[j] =  distance[index] + adj[index][j];
              }
          }
          checked[index] = true;
       }
      for(int i =1;i<nodeCount;i++)
      {
          if(distance[i] == Integer.MAX_VALUE)
           {
           System.out.println("INF");
           }
           
           else
           {
           System.out.println(distance[i]);
           }
      }
   }
   

}

 

 

 

 

그래서 눈물을 뒤로 하고 다시 list형태를 사용하는 형식으로 코딩했다.

 

List형식으로의 변수 선언이다.

기존에 2차원 배열이었던 부분을 ArrayList[] 형태로 바꾸었고,

list[1].get() 을하면, 1번에 연결된 것들을 가져온다고 생각하면된다.

BFS, DFS와 비슷하다

 

간단하게, list에 값들을 넣어주고, solve함수를 이용해서 최종 배열을 update 후에, print 하면 끝이다.

이제 제일 중요한 node에 대한 부분과 solve함수를 보자

 

우선 Node 클래스를 보자,

idx와 w를 변수로, 생성자가 이를 set해준다.

idx는 어떤 노드인지, 예를 들면, list[1] 에 list형태로이있는 node의 객체가 idx 가 3이고 w가 4라면,

3번과 4라는 가중치를 가지고 연결되어있는 것이다.

 

그러면 여기서, 한가지의 문, comparable과, compareTo는 왜있는 것일까?

 

이건 위에 sove함수를 보면된다.

기존 단순  큐가 아닌, PriorityQueue이다. 이건 뭘까? 바로 자바의 우선순위 큐이다.

이 우선순위 큐는 넣은대로, 나오는 것이아니라, 저 compare To 의 값이 큰순서대로,

즉 node의 w가 작은 순서대로 나온다. (더 조금 빼야 결과적으로는 크니까)

다시말하면, 처음에 배열에 int maxvalue 로 일괄 초기화를 했기때문에,

 

list[1]에 있는 녀석들이 전부 큐에 들어갈것이고, compareTo를 통해서, poll을 하게되면, Node는 현재

가지고있는 가장 작은 w를 가진 녀석이 return 된다.

 

이렇게 하게되면 전부

기존에 있던 타겟 거리 > 현재 노드까지의 거리 + 현재노드에서 타겟노드 거리

이런 check를 할수 있게 된다. (값이 없었어도, Arrays.fill을 통해서 int 최대를 넣었기 떄문에 해당 check에 걸린다.)

 

이렇게 풀면 ok가 된다.

 

그냥 더 빠른 알고리즘 하나만 익으면 될듯하다. 그냥 이 list를 활용한 방식으로 다 풀자;; ㅋㅋ

 

전체 코드

import java.util.*;

public class Main
{
    static int nodeCount,connCount,startNode;
    static ArrayList<Node> list [];
    static int dist[];
    static boolean checked[];
    
   public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    nodeCount = sc.nextInt();
    connCount = sc.nextInt();
    startNode = sc.nextInt();
    dist = new int[nodeCount+1];
    list = new ArrayList[nodeCount+1];
    checked = new boolean[nodeCount+1];
    
    for(int i=1;i<nodeCount+1;i++)
    {
        list[i] = new ArrayList<>();
    }
    
    Arrays.fill(dist,Integer.MAX_VALUE);
    
    dist[startNode] =0;
    for(int i =0;i<connCount;i++)
    {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int w = sc.nextInt();
        list[a].add(new Node(b,w));
    }
    solve();
    for(int i = 1;i<=nodeCount;i++)
    {
        if(dist[i] == Integer.MAX_VALUE)
            System.out.println("INF");
        else
            System.out.println(dist[i]);
    }
    
    
   }   
    
    public static void solve()
    {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(startNode,0));
        while(!pq.isEmpty())
        {
            Node a = pq.poll();
            if(checked[a.idx])
                continue;
            checked[a.idx] =true;
            for(Node o : list[a.idx])
            {
                if(dist[o.idx] > dist[a.idx] + o.w)
                {
                    dist[o.idx] = dist[a.idx] + o.w;
                    pq.add(new Node(o.idx,dist[o.idx]));
                }
            }
        }
    }
    
    static class Node implements Comparable<Node>
    {
        int idx,w;
        public Node(int idx,int w)
        {
            this.idx = idx;
            this.w = w;
        }
        public int compareTo(Node o)
        {
            return this.w - o.w;
        }
        
    }
}

 

 

 

 

 

* 특정 조건의 최단경로

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

1504번: 특정한 최단 경로

 

이 문제를 풀때는 한가지 기억해둬야하는 사항이 있다.

특정 경로를 거쳐야 한다면, 총 3번을 해야한다 (2가지의 경로를 꼭 거쳐야 한다면)

예를 들어서 1에서 시작해서 2와 3을 거쳐서 5로 도달한다고 예를 들자

 

그러면, 복잡하게 생각할 것 없이, 1-> 2    + 2-> 3 + 3-> 5 이렇게 갈떄의 최단거리를 각각 구해서, 더해주면된다.

그런데, 1 - 2 -3 - 5 이렇게 갈수도있고, 1 -3 -2 -5  이렇게 갈수도 있다.

따라서, 총 두가지 케이스를 구해서, 더 작은 값을 print 해주면된다.

코드 풀이를 보자.

 

우선 BFS 와 최단거리 알고리즘의 결합이라고 생각하면 좋다.

필요한 목록 ? 개념은 아래와 같다. 이건 암기를 해놓는 것이 좀 편한듯 하다

이해를 하면되지만, 실제 코테나, 시험을 보게된다면, 이해를 해서 떠올리기에는 시간이 없다 ㄷㄷ

 

1) Node class 개념, ArrayList<ArrayList<Node>> 의 개념이며,

list.get(1)의 Node list들은 , 1을 시작점으로 각각 연결되어있는 정보들이며,

정보는 Node 의 하위 end 정보와 가중치의 정보가 있다.

항상 우선순위 큐를 사용하기 위해, Comparable 을 impl 해줘서, compareTo를 Overrride 를 해줘야 한다

(안그러면, 일반큐에서 빼올때 일일히 연결된 노드 중, 가장 작은것을 구해서 가져와야한다.)

 

 

2) Static 변수로 필요한 것들은

총 방문했던 이력을 가지고있는 boolean 배열

최종 최단 거리를 가지고있는 int 배열

무한대를 표기할 final max 대부분, Integer.MAX_VALUE 를 하여, 자동 세팅하지만, 때때로 사용불가한 상황도있다.

ArrayList<ArrayList<Node>> 와 같이, 각 출발지 별로, 도착지와 가중치 정보를 담은 리스트

 

 

위의 사진은 간단히 문제 상 입력을 하는 부분에 대해서 담는 것이다.

양방향이라, 출발지 - 도착지, 도착지 - 출발지로 list 를 add해준다는 것이 조금 특이사항이다.

 

 

 

 

이런식으로, 총 2가지 케이스에 대해서, 함수로 각각 더하고, 마지막에 프린트를 해준다.

이제 findFunc 함수 구현체를 보자

 

 

 

우선 함수는 실행될때마다, 무조건 거리와, 방문에 대한 초기화를 해야한다. (여러번 재사용해야하기 때문에)

함수에서 전달 받은 시작점에 대한 setting 을 해준다 (거리 0 세팅) 그리고 우선 순위 큐에 offer해준다.

 

1. 방문체크하여 방문 업데이트 하고

2. 해당 노드에 대한 연결 list를 node.get(a.end)를 해서 가져오고

3. 해당 목적지가 방문하지않았고, 현재 저장되어있는 거리 정보보다, 현재노드 + 현재노드연결 가중치가 더 작다면 업데이트 해준다.

 

3번의 개념은 조금 헷갈리니까 쉽게 얘기한다면,

1->3 으로 가는게 기존에, 5로 dist에 담겨있었다고 가정하면,

1 ->2 로 가는 가중치가 1 , 2->3 으로 가는 가중치가 2일때 이 두개를 더했을때, 5보다 작으면, 2로 업데이트 한다는 것이다.

업데이트 하게되면, 이 값을 큐에 add 한다.

 

이 과정을 무한 반복하면, 특정 경로를 지나칠때의 케이스 2가지에 대한 최소 경로 합산한 게 2개씩 나오는데 

이중 작은것을 print 하면된다.

 

bfs와, 이 최단경로 알고리즘은 조금 빈번하게 출제 되고, 큰틀은 같지만, 살짝씩 변형을 좋아한다.

그리고 재미있다. 출퇴근 길이나, 왔다갔다가 하면서 조금 씩 눈에 익혀 놓는게 좋을것 같다.

코테는 시간싸움....ㄷㄷㄷ

 

 

 

전체 코드

import java.util.*;


public class Main
{
    static class Node implements Comparable<Node>
    {
    int end;
    int weight;
    
    Node(int end,int weight)
    {
        this.end = end;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Node o)
    {
        return weight - o.weight;
    }
    }
    
    static int nodeCount,connCount;
    static ArrayList<ArrayList<Node>> node;
    static boolean[] checked;
    static int[] dist;
    static final int maxNum = 200000000;
    
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    nodeCount = sc.nextInt();
    connCount = sc.nextInt();
    node = new ArrayList<>();
    dist = new int[nodeCount+1];
    checked = new boolean[nodeCount+1];
    Arrays.fill(dist,maxNum);
    
    for(int i =0;i<=nodeCount;i++)
    {
        node.add(new ArrayList<>());
    }
    for(int i =0;i<connCount;i++)
    {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int w = sc.nextInt();
        node.get(a).add(new Node(b,w));
        node.get(b).add(new Node(a,w));
        
    }
    
    int req1 = sc.nextInt();
    int req2 = sc.nextInt();
    
    int result1 = 0;
    result1 += findFunc(1, req1);
    result1 += findFunc(req1, req2);
    result1 += findFunc(req2, nodeCount);
    
    int result2 = 0;
    result2 += findFunc(1, req2);
    result2 += findFunc(req2, req1);
    result2 += findFunc(req1, nodeCount);
    
    if(result2 >= maxNum && result1 >= maxNum)
        {
            System.out.print(-1);
        }
    else{
        if(result2 >= result1)
        {
            System.out.print(result1);
        }
        else{
            System.out.print(result2);
        }
    }
    
    }
    
    static int findFunc(int start, int end)
    {
        Arrays.fill(dist,maxNum);
        Arrays.fill(checked,false);
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        //첫번째 값 세팅
        pq.offer(new Node(start,0));
        dist[start] = 0;
        
        while(!pq.isEmpty())
        {
            Node a = pq.poll();
            
            if(!checked[a.end]){
                checked[a.end] =true;
                
                //종료지점에서,연결된 노드들을 체크
                for(Node ai : node.get(a.end))
                {
                    //현재 최단 타겟 거리 > 현재까지 거리 + 현재 노드~타겟까지거리
                    if(!checked[ai.end] && dist[ai.end] > dist[a.end] + ai.weight)
                    {
                         dist[ai.end] = dist[a.end] + ai.weight;
                         pq.add(new Node(ai.end,dist[ai.end]));
                    }
                }
            
                
            }
        }
        return dist[end];
        
    }
    
    
  
}