다익스트라 알고리즘 기본 문제(각 정점의 최소 거리비용 출력)풀이

이러한 그래프가 있을때.

1번 정점에서 각 정점으로 가는 최소 거리비용을 출력하라.

 

입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보와 거리비용이 주어진다.

출력설명
1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요.

입력은 이렇게 들어온다

6 9 // 정점이 1~6 간선은 9개 존재. 
1 2 12 // 1번 정점에서 2번 정점으로 가는데 가중치(거리비용)는 12다
1 3 4 // ...
2 1 2 
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

 

다익스트라 알고리즘으로 문제를 풀텐데 중요하게 알아야 할 점이 있다.

*다익스트라 알고리즘은 가중치가 음수이면 사용할 수 없다

 이 문제는 해당사항이 없으니 넘어간다.

 

 

이 문제를 풀기 위해 핵심적으로 필요한 자료형은 다음과 같다.

1.

int [] dis = new int[n+1];

dis는 각 정점의 최소이동거리를 담을 정수형 배열. n=6이면

dis 배열은 1~6까지 사용하고 최소거리를 구해야 하기에 가장 높은 정수로 초기화 한다.

Arrays.fill(dis, Integer.MAX_VALUE);

 

2.

graph = new ArrayList<ArrayList<Edge>>();

리스트형 자료형으로 각 정점 별 가중치 정보를 입력받는다.

 

 

3.

class Edge

간선 정보를 저장할 클래스 선언. 

vex는 정점 cost는 거리비용 정보가 담긴다

또한 최소거리비용 문제이므로 cost 오름차순 정렬

class Edge implements Comparable<Edge> {
    int vex;
    int cost;
    Edge(int to,int cost){
        this.vex=to;
        this.cost=cost;
    }
    //ArrayList에서는 Collections.sort(변수명)해야 적용되지만
    //우선순위 큐에서는 poll()하면 자동으로 처리됨.
    @Override
    public int compareTo(Edge e){
        return this.cost - e.cost;
    }
}

4.

 

PriorityQueue<Edge> pQ = new PriorityQueue<>();

우선순위 큐로 dis배열에 정점의 최소거리 비용이 갱신되면 

연결된 정점의 거리계산을 위해 사용된다.

 

* 알고리즘 순서

1. 각 정점별 간선 정보를 graph변수에 담고 ,  해를 구하는 solution()함수의 매개변수로 

시작정점인 1을 넣고 호출.

Arrays.fill(dis, Integer.MAX_VALUE);//배열 값 초기화
graph = new ArrayList<ArrayList<Edge>>();//각 정점 별 가중치 정보
for(int i=0;i<=n;i++) graph.add(new ArrayList<Edge>());//정점 수 만큼 할당
for(int i=0;i<m;i++){
    int a = kb.nextInt();
    int b = kb.nextInt();
    int c = kb.nextInt();
    graph.get(a).add(new Edge(b,c));
}
M.solution(1); // 시작 정점은 1

2-1. solution함수에서 우선순위 큐 , dis 배열 시작정점 값으로 초기화

PriorityQueue<Edge> pQ = new PriorityQueue<>();
pQ.offer(new Edge(start,0));// 출발 정점 초기화
dis[start]=0;// 출발 정점 초기화

2-2. solution함수에서 우선순위 큐 선언 및 시작정점 값으로 초기화

//우선순위 큐가 빌 때까지
while(!pQ.isEmpty()){
    Edge tmp=pQ.poll();
    int now=tmp.vex;
    int nowCost=tmp.cost;
    //최소거리를 찾았으면 또 탐색할 필요없음
    if(nowCost>dis[now]) continue;
    for(Edge ob : graph.get(now)){
        //최소거리 갱신
        if(dis[ob.vex]>nowCost+ob.cost){
            dis[ob.vex]=nowCost+ob.cost;
            pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
        }
    }
}

이 부분이 핵심코드이기에 조금 길게 설명하겠다.

while문이 처음 실행되면 위에서 시작정점을 초기화 한다고 한 것과 같이
 dis 배열에는 다음과 같이 되어있다. (M 은 Integer.MAX_VALUE를 뜻함)

0

M

M

M

M

M

우선순위 큐는  다음과 같이 되어있다

(1,0)

Edge tmp=pQ.poll();
int now=tmp.vex; // 1
int nowCost=tmp.cost; //0

시작정점 초기화로 인해 위와 같이 변수에 값이 할당되고

for(Edge ob : graph.get(now)){
    //최소거리 갱신
    if(dis[ob.vex]>nowCost+ob.cost){
        dis[ob.vex]=nowCost+ob.cost;
        pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
    }
}

위 코드로 인해

1번 정점과 연결된 가중치 정보를 graph 에서 찾는다. 입력을 보면 1번 정점에서 갈 수 있는 간선정보는

1 2 12 // 1번 정점에서 2번 정점으로 가는데 가중치(거리비용)는 12다
1 3 4 // 1번 정점에서 3번 정점으로 가는데 가중치(거리비용)는 4다

.

.

.

이렇다면

 dis 배열에는 다음과 같이 변한다

0

12

4

M

M

M

우선순위 큐는  다음과 같이 되어있다

(2,12) (3,4)

이 과정들이 계속 반복된다. 

단, 방금 예시는 시작정점의 거리비용이 바로 dis배열에 가중치 값이 할당되는거 같지만 

dis[ob.vex] = nowCost+ob.cost;//최소비용일 경우 최신화

위 코드처럼 알고보면 0+12 , 0+4 라는 계산으로 위와 같이 되었다는 것을 알 수 있다.

큐를 사용하는 것과 코드를 짜는 방식이 BFS문제와 유사한 방식으로 느껴지는데 우선순위 큐에 대한 개념을 잘 알고 가야겠다. 끝.

 

 

 

 

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 김태원