[BFS] 최단 경로 출력하기 (Java)

문제

다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선 수를 출력해보자.

 

입력 설명

첫째 줄에는 정점의 수 N (1 <= N <= 20) 과 간선의 수 M 이 주어진다.

그 다음부터  M 줄에 걸쳐 연결정보가 주어진다.

 

출력 설명

1번 정점에서 각 정점으로 가는 최소 간선 수를 2번 정점부터 차례대로 출력 

 

입출력 예제

입력 예제
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

 

풀이

(처음에 한 번 동영상을 보고 나서 아 그렇구나... 하고 넘어가져서 알게 된 줄 알았다.

역시나 오산이었다. 

이틀 후 다시 풀어보니 전혀 생각이 안났다......)

 

현재는 정점이 많지 않지만 정점이 많아지면 인접행렬은 비효율적이므로 인접리스트로 구현한다.

 

1. 정점 graph 세팅 (인접리스트)

각 정점은 graph에서 인덱스로 접근한다고 가정하며,

각각의 정점은 연결된 정점들(int 요소) 정보를 담고 있는 인접 리스트이다. 

그러므로 정점을 담고있는 ArrayList<Integer> 들의 ArrayList 가 graph 가 된다. 

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

0 번 인덱스는 없는 셈 취급하고,  graph 는 n개의 정점을 표시하기 위해 n번 인덱스까지 있어야 한다.

그리고 그 n 번 인덱스까지 먼저 빈 ArrayList<Integer> 를 채워 넣는다. 

이후 입력되는 연결 정보를 각각의 정점 정보에 맞게 추가해 준다. 

 

위의 예시로 보자면,

맨 첫 줄에 입력되는 정보는 정점의 개수 6이고, 연결된 간선의 수는 9이다.

그러므로 첫 줄을 입력 받은 후, 0번 인덱스부터 6번 인덱스까지 총 7개의 빈 new ArrayList<Integer> 를 추가해 준다.  (그 전에 graph 선언 및 초기화... 나는 귀찮아서 전역으로 선언하고 초기화했다.)

// 전역 graph 선언
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); // 정점 개수
    int m = sc.nextInt(); // 간선 개수

    // graph 에 정점에 해당하는 인덱스까지 빈 리스트 추가
    for(int i = 0; i <= n; i++) {
        graph.add(new ArrayList<Integer>);
    }
}

연결된 정점을 담을 빈 리스트들이 생겼으니 이제 한줄씩 연결정보를 입력받아서 정점을 추가해준다.

public static void main(String[] args) {
	// ...
    // 간선 정보 추가
    for(int i = 0; i < m; i++) { // 총 m개의 연결 정보
        // a b : a -> b 로 연결된 간선
        int a = sc.nextInt();
        int b = sc.nextInt();
        graph.get(a).add(b);
    }
}

a 정점에서 b 로 가는 간선을 추가해야 하므로, a 정점에 해당하는 ArrayList 에 b 값을 추가해야 한다.

그러므로 graph.get(a) 로 a 정점 리스트를 불러와서 거기에 .add(b) 로 b 값을 넣어준다. 

 

2. 방문한 정점을 체크할 배열(check)과 각 정점의 최단 경로를 기록할 배열(distance) 선언

이제 1번 정점에서 시작하여 레벨 탐색 방식(BFS)으로 모든 정점을 탐색해나갈 것이다. 

이 때 최단 경로를 탐색해야 하므로 이미 방문한 정점은 다시 방문하지 않아야 하고, 

각 정점을 방문할 때의 레벨(최단 경로)이 몇이었는지를 기록할 배열을 선언해둔다. 

 

역시 인덱스를 정점으로 간주할 것이기 때문에 두 배열 모두 n+1 크기로 초기화해준다. 

(전역으로 선언한 후 메서드 내에서 초기화했다.)

// 전역 선언
static int[] check, distance;

public static void main(String[] args) {
   // ...
   check = new int[n + 1];
   distance = new int[n + 1];
}

 

(드디어 사전 작업이 끝났다...)

 

3. BFS 탐색

조금 복잡하니 static void bfs(int start) {} 메서드를 하나 추가해서 따로 작성해보자.

먼저 Queue 를 선언해주고, 큐에 시작 지점 정점을 넣는다. 

public static void bfs(int start) { // start : 시작 정점
	Queue<Integer> queue = new LinkedList<>();
    queue.add(start);

	check[start] = 1; // 스타트 지점 방문했음으로 체크
    distance[start] = 0; // 스타트 지점으로의 최단 경로값은 0으로 초기화
}

start 정점에 대해 check 배열과 distance 배열의 초기값도 지정해준다. 

 

이제 queue 가 빌 때까지 while 문을 반복할 것이다.

먼저 현재 정점을 큐에서 꺼내온다. (정점은 항상 연결된 정점들을 요소로 갖는 하나의 리스트이다.)

꺼내온 정점 리스트에 들어있는 연결된 정점들을 하나씩 순회해서 확인해서

그 연결된 각각의 정점이 방문한 적이 없는 정점이라면?

1. check 배열의 방문상태를 체크해주고,

2. queue에 해당 정점을 추가해주고,

3. 해당 정점까지의 최단경로(해당 정점을 방문했을 때의 레벨값 = 이전 정점에서의 레벨 + 1)값을 distance 배열에 기록해준다. 

while(!queue.isEmpty()) {
    int curNode = queue.poll(); // 현재 노드 꺼내옴. (최초에는 스타트 지점인 1)

    // graph.get(curNode) : curNode 에서 연결된 정점들이 저장된 리스트
    for(int nextNode : graph.get(curNode)) {
        // 만약 curNode 에 연결된 정점들 중에서 nextNode 가 방문하지 않았던 노드라면
        if(check[nextNode] == 0) {
            check[nextNode] = 1; // 방문 상태 체크하고,
            queue.add(nextNode); // 해당 노드 nextNode 를 queue 에 넣고,
            distance[nextNode] = distance[curNode] + 1; // nextNode 의 distance 를 기록한다.
            // nextNode 의 최단 경로는 현재 레벨 + 1 이라고 생각할 수 있다.
        }
    }
}

 

4. 마지막으로 각 정점으로의 최단 경로를 출력해보자. 

public static void main(String[] args) {
		// ...
		for(int i = 2; i <= n; i++) {
		System.out.println(i + " : " + distance[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

정상적으로 출력된다~

 

전체 코드

import java.util.*;

public class Test {
    static int n, m; // n 개의 정점, m 개의 연결 정보

    // m개의 연결 정보(간선 정보) 를 담을 인접리스트 graph;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    static int[] check, distance; // 방문 여부를 체크할 check 배열, 각 정점(인덱스)의 최단경로를 기록할 distance 배열

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        check[start] = 1; // 스타트 지점 방문했음으로 체크
        distance[start] = 0; // 스타트 지점에서 스타트지점까지의 최단 경로 0으로 초기값 설정

        while(!queue.isEmpty()) {
            int curNode = queue.poll(); // 현재 노드 꺼내옴. (최초에는 스타트 지점인 1)

            // graph.get(curNode) : curNode 에서 연결된 정점들이 저장된 리스트
            for(int nextNode : graph.get(curNode)) {
                // 만약 curNode 에 연결된 정점들 중에서 nextNode 가 방문하지 않았던 노드라면
                if(check[nextNode] == 0) {
                    check[nextNode] = 1; // 방문 상태 체크하고,
                    queue.add(nextNode); // 해당 노드 nextNode 를 queue 에 넣고,
                    distance[nextNode] = distance[curNode] + 1; // nextNode 의 distance 를 기록한다.
                    // nextNode 의 최단 경로는 현재 레벨 + 1 이라고 생각할 수 있다.
                }
            }
            // for 문을 한 번 반복할 때마다 레벨이 증가하게 된다.
            // 더이상 갈 수 있는 노드가 없을 때까지 while 문 반복하며 distance 기록
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        // graph 에 인덱스 n 까지 빈 ArrayList<Integer> 채워넣기
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 연결 정보를 인접리스트 graph 에 추가하기
        for(int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }

        // check 배열과 distance 배열 초기화
        check = new int[n+1];
        distance = new int[n+1];

        bfs(1);

        // 스타트 지점 1번에서 나머지 정점으로의 최단 경로 출력하기
        for(int i = 2; i <= n; i++) {
            System.out.println(i + " : " + distance[i]);
        }
    }
}