★경로 탐색(인접 행렬, DFS)

방향 그래프의 1번 정점에서 n번 정점으로 가는 모든 경로의 가지 수를 출력하시오.

첫 줄은 정점 , 간선 수

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5 

 

무방향 그래프 - graph[a][b] = 1 / graph[b][a] = 1

방향 그래프 - graph[a][b] = 1

가중치 방향 그래프 - graph[a][b] = c

 

정점 갯수가 많아지면 인접행렬은 메모리 낭비와 시간 복잡도가 길어진다.

그때 인접리스트 사용하면 된다. 현재는 인접행렬로 연습.

 

인접행렬은 N제곱 크기 만큼 배열로 만들어야 하므로 정점이 많아질 때 인접리스트를 사용하는게 좋다.

그리고 갈 수 있는 정점을 확인하는것도 N만큼 계속 돌아야한다..

정점이 10000개이면 10000 * 10000 만큼의 배열이 필요하고

해당 정점에서 10000개의 정점으로 갈 수 있는지 매번 확인해봐야 한다...

 

인접리스트는 처음부터 해당 정점에서 갈 수 있는 정점만 추가한 것이므로 성능상 매우 좋다.

각 정점에서 갈 수 있는 정점들을 넣어놨으므로 갈 수 있는지 확인할 필요가 없고

따라서 해당 정점이 방문한 노드인지 아닌지만 따지면 된다.

 

하지만 노드 1과 7이 연결되어 있는 경우 인접 행렬 방식은 graph[1][7]만 확인하면 되지만 인접 리스트 방식은 1에 대한 인접 리스트를 앞에서부터 차례대로 확인하게 되어 연결 정보를 얻는데에는 느리긴하다.

 

방문한 정점에 대해서 체크해주는 배열이 필요하다.

여기서 방문 처리의 이유는 경로가 무한으로 만들어질 수 있기 때문이다.

1->2->5   1->2->1->2->5 같은..

다른 경로도 탐색해봐야하기 때문에 경로가 만들어진 뒤 방문 체크를 풀어준다.

인자로는 시작 정점인 1을

매개변수로는 마지막 정점인 n으로 설정해주었음

import java.util.*;

public class Main {
    static int n, m, answer = 0;
    static int[][] graph;
    static int[] ch; //방문여부 체크

    public void DFS(int v) { //초깃값 v = 1
        //n번(5번) 정점에 도착했으면 하나의 경로가 만들어짐
        if(v == n) answer++;
            //n번(5번) 정점이 아니고 n번을 향해 더 뻗어나가야하면
        else {
            //v번 노드에서 1번 노드부터 n번 노드까지 뻗어볼거임
            for(int i = 1; i <= n; i++) {
                //현재의 지점인 v번 정점에서 i번 정점으로 갈 수 있냐 && 방문 안했냐
                if(graph[v][i] == 1 && ch[i] == 0) {
                    ch[i] = 1;
                    DFS(i);
                    //다른 정점들도 확인해봐야하므로 방문한 정점 미방문으로 체크
                    ch[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); //노드의 갯수(정점의 갯수)
        m = kb.nextInt(); //간선의 갯수
        graph = new int [n+1][n+1]; //정점 번호
        ch = new int[n+1];
        //a에서 b로 간다는 의미.
        for(int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph[a][b] = 1;
        }
        ch[1]=1;
        T.DFS(1);
        System.out.println(answer);
    }

}

 

1번 정점에서 2,3,4번 정점 갈 수 있음

2번 정점에서 1,3,5번 정점 갈 수 있음

3번 정점에서 4번 정점 갈 수 있음

4번 정점에서 2,5번 정점 갈 수 있음

 

ch[1] = 1 / v = 1

D(1) - 먼저 2번 정점으로 가는 경우를 처리 (3,4번 남아있음)

1->2

ch[2] = 1 / D(2) 호출 17라인 멈춤

D(2) - 1번은 못가고 3번 정점으로 가는 경우를 처리 (5번 남아있음)

1->2->3

ch[3] = 1 / D(3) 호출 17라인 멈춤

D(3) - 4번 정점으로 가는 경우를 처리

1->2->3->4

ch[4] = 1; / D(4) 호출 17라인 멈춤

D(4) - 2번은 못가고 5번 정점으로 가는 경우를 처리

1->2->3->4->5

ch[5] = 1; / D(5) 호출 17라인 멈춤

v == 5 n == 5 / v == n 이므로 5번 정점 도착. 1->2->3->4->5로 갈 수 있음(answer = 1)

 

D(4)의 17라인 다시 돌아와서 ch[5] = 0로 만들고 끝

1->2->3->4

D(3)의 17라인 다시 돌아와서 ch[4] = 0로 만들고 끝

1->2->3

D(2)의 17라인 다시 돌아와서 ch[3] = 0로 만들고 5번 정점으로 가는 경우를 처리

1->2->5

 

ch[5] = 1; / D(5) 호출 17라인 멈춤

v == 5 n == 5 / v == n 이므로 5번 정점 도착. 1->2->5로 갈 수 있음(answer = 2)

 

D(2)의 17라인 다시 돌아와서 ch[5] = 0로 만들고 끝 

1->2

D(1)의 17라인 다시 돌아와서 ch[2] = 0로 만들고 3번 정점으로 가는 경우를 처리(4번 남아있음)

1->3

ch[3] = 1; / D(3) 호출 17라인 멈춤

D(3) - 4번 정점으로 가는 경우를 처리

1->3->4

ch[4] = 1; / D(4) 호출 17라인 멈춤

D(4) - 2번 정점으로 가는 경우를 처리(5번 남아있음)

1->3->4->2

ch[2] = 1; / D(2) 호출 17라인 멈춤

D(2) - 1번은 못가고, 3번도 못가고 5번 정점으로 가는 경우를 처리

1->3->4->2->5

 

ch[5] = 1; / D(5) 호출 17라인 멈춤

v == 5 n == 5 / v == n 이므로 5번 정점 도착. 1->3->4->2->5로 갈 수 있음(answer = 3)

 

D(2)의 17라인으로 다시 돌아와서 ch[5] = 0로 만들고 끝

1->3->4->2

D(4)의 17라인으로 다시 돌아와서 ch[2] = 0로 만들고 5번 정점으로 가는 경우를 처리

1->3->4->5

 

ch[5] = 1; / D(5) 호출 17라인 멈춤

v == 5 n == 5 / v == n 이므로 5번 정점 도착. 1->3->4->5로 갈 수 있음(answer = 4)

 

D(4)의 17라인으로 다시 돌아와서 ch[5] = 0로 만들고 끝

1->3->4

D(3)의 17라인으로 다시 돌아와서 ch[4] = 0로 만들고 끝

1->3

D(1)의 17라인으로 다시 돌아와서 ch[3] = 0로 만들고 4번 정점으로 가는 경우를 처리

1->4

ch[4] = 1; D(4) 호출 17라인 멈춤

D(4) - 2번 정점으로 가는 경우를 처리(5번 남아있음)

1->4->2

ch[2] = 1; / D(2) 호출 17라인 멈춤

D(2) - 1번으로는 못가고 3번 정점으로 가는 경우를 처리(5번 남아있음)

1->4->2->3

ch[3] = 1; D(3) 호출 17라인 멈춤

D(3) - 4번 정점으로 못가고 갈 수 있는 곳이 없음

D(2)의 17라인으로 돌아와서 ch[3] = 0으로 만들고 5번 정점으로 가는 경우를 처리

1->4->2->5

 

ch[5] = 1; / D(5) 호출 17라인 멈춤

v == 5 n == 5 / v == n 이므로 5번 정점 도착. 1->4->2->5로 갈 수 있음(answer = 5)

 

D(2)의 17라인으로 돌아와서 ch[5] = 0으로 만들고 끝

1->4->2

D(4)의 17라인으로 돌아와서 ch[2] = 0으로 만들고 5번 정점으로 가는 경우를 처리

1->4->5

 

ch[5] =1; / D(5) 호출 17라인 멈춤

v == 5 n == 5 / v == n 이므로 5번 정점 도착. 1->4->5로 갈 수 있음(answer = 6)