자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Graph/BFS_최단거리)

 

 

14. 그래프 최단거리(BFS)

 

예시 입력 1 

6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5

예시 출력 1

2 : 3
3 : 1
4 : 1
5 : 2
6 : 2

 

1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.

1번 정점에서 2번정점을 간다고 하면 1->4->6->2 라서 총 3번이다.

1->3->4->6으로 갈 수 도 있지만 4번만에 가서 최단 간선수는 아니다.

1번은 0레벨이고, 1레벨만에 가는건 3,4번이라서 큐에 3,4번이 들어간다.

3,4는 1레벨이고 한번만에 간다는 의미이다. 이런식으로 레벨로 할 수 도 있다

1레벨 돌때, 큐에서 3,4가 나올텐데, for문 2바퀴 돌면서 탐색한다. 3에서 나올 수 있는건 4인데, 이미 체크된거라서 갈 필요 없다.

4에서 갈 수 있는건 5,6번이라 레벨 2입니다.

 

이런식으로 레벨로 할 수 있지만, 다른 방법인 배열로 할 수 있는 방법도 할 수 있는 방법을 알아야 합니다.

dis의 인덱스 번호의 의미에 대해 알아보겠습니다.

dis[3]은 1번 정점에서 3번정점까지 가는데 최소 간선 수를 저장합니다.

 

1번 정점에서 1번 정점은 갈 필요없어서 0으로 초기화하고,

1번에서 갈 수 있는걸 탐색해야합니다. 인접리스트로 해도 됩니다. 인접리스트로 할 경우 3,4가 추가되어 있을 것입니다.

3,4는 1번 정점에서 오는 것이기 때문에, 1번 정점까지 오는건 0이고, 1번값 플러스 1을 해준다.  0 + 1해서 이런식으로 된다.

1번 정점이 v라고 가정하면, dis의 인덱스는 nx(next vertex)입니다.

v에서 nv로 오니까 +1을 해줘야 합니다. dis[v]는 v까지 가는 최소 거리입니다.

 

큐에서 1번은 빠졌고 3,4를 넣어줍니다. 큐에서 3이 나옵니다. 방문했으면 체크해야하는데, 큐에 들어가는 순간 체크해주세요.

3에서 갈 수 잇는거 인접리스트에 있을텐데, 4는 이미 잇으니까 패스한다.

이제 4가 나오면, 4의 인접리스트에는 5,6이 있을텐데, 4번에다가 5번 정점가는데 최소거리는 1입니다.

5를 큐에다 넣고 5는 1+1하니까 2가 됩니다.

6번 정점도 큐에 들어가고, 체크하고, 4번정점에서 가는거라서 1+1 해서 2입니다.

이제 5가 나오면 인접리스트에 원소가 없으므로, 끝나는거고 6이 나오면 큐에 2가 들어가고, 체크 걸고

2번은 6번에서 온 것이므로 2+1는 3입니다.

큐에서 2 나와봤자 갈때가 없어서 끝나버립니다.

이렇게 채워진 dis는 최단거리로 저장되어있는데, 출력할때 or문을 2번부터 돌면서 그냥 쭉 값을 찍어주면 됩니다.

1번에서 4번 갈때 최단거리로 갈 수 있어서 먼저 방문해버리는데, BFS는 이렇게 절대 돌아서 가지 않습니다.

먼저 최단거리 방문해버리고 체크해버리면, 돌아서 가는건 체크되어있어서 갈 수가 없습니다.

그리고 이런식으로 배열에 기록할 수 있습니다. 1차원에서는 레벨로 해도 되지만 2차원에서는 2차원 배열에 기록합니다.

 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n, m;
    static ArrayList<ArrayList<Integer>> graph;
    // 체크배열, dis배열
    static int[] ch, dis;

    public void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        ch[v] = 1;
        dis[v] = 0;
        queue.offer(v);
        while (!queue.isEmpty()) {
            int cv = queue.poll(); // 현재 정점을 꺼내기
            // 인접리스트라서 for each문 사용
            // cv와 연결된 것들을 하나 씩 꺼내 준다.
            for (int nv : graph.get(cv)) {
                // 다음 정점을 방문 안했다면
                if (ch[nv] == 0) {
                    ch[nv] = 1; // 방문했다고 체크하고
                    queue.offer(nv); // 큐에 넣기
                    // nv는 cv에서 간선 타고 왔음
                    dis[nv]= dis[cv]+1; // 굉장히 중요!!
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        ch = new int[n + 1];
        dis = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            // get(0) 하면 첫번째, get(1) 하면 두번째
            graph.get(a).add(b);
        }
        T.BFS(1);
        // 1번 부터 특정 노드까지 최대간선수를 출력하는거라, i는 2부터 시작
        // 1번은 dis배열에 0으로 저장되어있을 것이고, 0번 인덱스는 필요 없음
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + dis[i]);
        }
    }
}

// 입력
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5
// 출력
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2