[JAVA] 자바 그래프 경로탐색 DFS 인접행렬, 인접리스트

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.

아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지입니다.

1 2 3 4 5

1 2 5

1 3 4 2 5

1 3 4 5

1 4 2 5

1 4 5

 

 

입력 

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

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

 

 

출력 

총 가지수를 출력한다.

예시 입력 1 

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

 

예시 출력 1

6

 

 

 

경로 탐색(인접행렬)

코드

import java.util.Scanner;

public class 경로탐색DFS_인접행렬 {
    static int n, m, answer=0;
    static int[][] graph;
    static int[] ch;
    public void DFS(int v){
        if(v==n) answer++;
        else {
            for (int i = 1; i <= n; i++) {
                if(graph[v][i]==1 && ch[i]==0) { //간선이 있고, 탐색하지 않은 노드인 경우
                    ch[i]=1;
                    DFS(i);
                    ch[i]=0;
                }
            }
        }
    }

    public static void main(String[] args) {
        경로탐색DFS_인접행렬 T = new 경로탐색DFS_인접행렬();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        for (int i = 0; i < m; i++) { //인접행렬
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}

그래프의 인접행렬

재귀적으로 호출하기 위해 확인해야 할 조건

1) graph에서 정점 사이에 간선이 있는가? ==> 인접행렬 graph에서 확인

2) 이전에 방문한 노드인가? ==> ch 배열 확인 (1인 경우 방문, 0인 경우 미방문)

 

DFS() 호출 후 해당 정점의 ch 배열의 값을 0으로 바꿔줘야 다음 경로를 찾을 때 해당 정점을 고려할 수 있음.

 

 

 

 

경로 탐색(인접리스트)

n이 커질수록 인접행렬을 사용했을 때 성능이 떨어진다(메모리도 많이 차지하고, 시간복잡도도 떨어짐)

이 경우 인접리스트를 사용해 해당 정점과 연결되어 있는 정점들만 확인하는 방법을 사용하면 된다.

코드

import java.util.ArrayList;
import java.util.Scanner;

public class 경로탐색DFS_인접리스트 {
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    public void DFS(int v){
        if(v==n) answer++;
        else {
            for(int nv : graph.get(v)) {
                if(ch[nv]==0) {
                    ch[nv]=1;
                    DFS(nv);
                    ch[nv]=0;
                }
            }
        }
    }
    public static void main(String[] args) {
        경로탐색DFS_인접리스트 T = new 경로탐색DFS_인접리스트();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        ch = new int[n+1];
        for (int i = 0; i <= n; i++) { //인접리스트
            graph.add(new ArrayList<Integer>());
        }
        ch[1] = 1;
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        T.DFS(1);
        System.out.println(answer);
    }
}

그래프의 인접리스트

ArrayList<Integer>를 담을 수 있는 ArrayList를 만들어 정점 사이 연결 정보를 저장한다.

graph.get(1)이라고 하면 정점 1에 연결되어 있는 2 - 3 - 4를 반환해 주어, 반환된 정점들에 순차적으로 접근할 수 있게 된다.

JAVA의 경우 포인터가 없어서 불편하지만, 이렇게 ArrayList를 담을 수 있는 ArrayList를 사용하면 된다.

 

 

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

코드를 통해 헤드 포인터가 되는 정점, 해당 정점과 연결된 정점들의 정보를 가진 정점을 생성해주고

 

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

코드를 통해 입력된 연결 정보를 통해 그림의 인접리스트를 완성한다.

 

 

 

 

결과

 

 

 

 

 

출처 : 인프런 자바 알고리즘 문제풀이 입문 : 코딩테스트 대비