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

1. 문제

1번 정점으로부터 각 정점으로 가는 최소 간선 수를 차례대로 출력하시오.

 

입력

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

 

2 - 1. 나의 풀이

ArrayList, Queue 를 사용한다는 걸 보고 바로 풀이에 들어갔다. (풀이 도구에 대한 힌트만 봤다.)

 

간선의 길이를 나타내는 변수 L을 설정했다.

BFS의 흐름을 따라가는 코드를 작성하는 건 쉬웠지만
L을 제대로 저장하기가 쉽지 않았다.

//실패한 초기 코드
while(!q.isEmpty()){
    int tmp = q.poll();
    L++;
    for (int x : graph.get(tmp)) {
        if (ch[x] == 0) {
            ch[x] = 1;
            q.offer(x);
            dis[x] = L;
        }
    }
}

위 코드가 틀린 이유는 정점을 지날 때(큐에서 꺼낼 때)마다 L이 증가되는데

3번 또는 5번 정점을 지날 때는 L이 증가되지 않아야하기 때문이다.

3번 정점의 다음은 4번 정점인데 이미 지나간 정점이고, 5번 정점은 다음을 가리키는 정점이 없기 때문이다.

 

이를 해결하기 위해서 flag 변수를 세웠다. (flag가 true일 때 L을 증가시킨다.)

큐에서 꺼낸 V가 E를 지나가려고 할 때

해당 E가 체크배열의 값이 1인 경우 (이미 지나간 경우)

또는 해당 E의 다음 정점값이 없는 경우(ArrayList.size() == 0) 

위 두 상황에서는 flag를 false로 표시해 L을 증가시키지 않는다.

다음과 같이 코드를 수정해서 풀었다.

while(!q.isEmpty()){
    int tmp = q.poll();
    flag = true;
    if(graph.get(tmp).size() == 0) flag = false; //다음 정점이 없는 경우
    for (int x : graph.get(tmp)) {
        if (ch[x] == 0) {
            ch[x] = 1;
            q.offer(x);
            dis[x] = L;
        }else flag = false; //ch[x] !=0 일 경우
    }
    if(flag)L++;
}

 

 

2 - 2. 나의 코드

package BFS_DFS;
import java.util.*;

public class BFS14 {
    public static int[] ch; //초기화 해야함
    public static int[] dis; //초기화 해야함
    public static ArrayList<ArrayList<Integer>> graph; //초기화 해야함
    public static int n = 0, m = 0, L = 0;
    public static boolean flag = true;

    public static void BFS(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(n);

        while(!q.isEmpty()){
            int tmp = q.poll();
            flag = true;
            if(graph.get(tmp).size() == 0) flag = false;
            for (int x : graph.get(tmp)) {
                if (ch[x] == 0) {
                    ch[x] = 1;
                    q.offer(x);
                    dis[x] = L;
                }else flag = false; //ch[x] !=0 일경우
            }
            if(flag)L++;
        }
    }

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

        ch = new int[n + 1];
        ch[1] = 1;
        dis = new int[n + 1];
        graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            int v = sc.nextInt();
            int e = sc.nextInt();
            graph.get(v).add(e);
        }

        BFS(1);
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + dis[i]);
        }
    }
}

 

3 - 1. 강의 풀이

BFS로 정점에 접근하는 건 강의과 같았으나 간선의 길이를 저장하는 방식이 달랐다.

전체적인 풀이 흐름은 큐에서 꺼낸 값(tmp)가 V가 되고 정점 tmp와 연결된 정점들 (E)를 체크후 다시 큐에 넣는 방식이다.

 

이때 체크를 한다음 조건에 만족하면 dis[E] = dis[V] + 1;의 방식으로 거리를 저장하면 된다.

 

이렇게 함으로 더 쉽고 코드 길이를 줄일 수 있다.

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;

public class BFS14 {
    public static int[] ch; //초기화 해야함
    public static int[] dis; //초기화 해야함
    public static ArrayList<ArrayList<Integer>> graph; //초기화 해야함
    public static int n = 0, m = 0, L = 0;
    public static boolean flag = true;

    public static void BFS(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(n);

        while (!q.isEmpty()) {
            int tmp = q.poll();
            //v: tmp, e: x
            for (int x : graph.get(tmp)) {
                if (ch[x] == 0) {
                    ch[x] = 1;
                    q.offer(x);
                    dis[x] = dis[tmp] + 1;
                }
            }
        }
    }

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

        ch = new int[n + 1];
        ch[1] = 1;
        dis = new int[n + 1];
        graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            int v = sc.nextInt();
            int e = sc.nextInt();
            graph.get(v).add(e);
        }

        BFS(1);
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + dis[i]);
        }
    }
}

 

 

4. 얻어갈 점

다양한 풀이를 시도해보려고는 하지만 그러기 쉽지가 않다.