자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Graph/DFS_경로탐색_인접리스트)

 

 

13. 경로탐색(인접리스트, ArrayList)

 

예시 입력 1 

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

예시 출력 1

6

정점이 1000개 10000개로 들어온다면 인접행렬로는 비효율적이다.

왜냐하면 정점이 5라고하고 5행 5열로 잡으면 된다. 1번 정점에서 갈 수 있는 정점이 어디인지 탐색하는데,

100개 정도까지는 괜찮지만 1000개 10000개라고 하면 인접행렬이라는 그래프로 할때 10000x10000을 해야해서 메모리를 크게 잡습니다. 그리고 1번 정점에서 갈 수 있는걸 찾으려면 1부터 10000까지 for문을 다 돌아야 합니다.

메모리랑 시간복잡도 면에서 너무 비효율적입니다.

 

그래서 이럴때 인접리스트를 사용합니다.

N이 5라고 가정했을때,

1번 리스트부터 5번 리스트까지 만들어 놓습니다. 그리고나서 간선정보가 들어오면 arrayList에 추가합니다.

arrayList는 원소를 추가만 하면 됩니다.

 

이렇게 하면 1번 정점을 체크하고 갈 수 있는 곳을 탐색하려면 arrayList만 탐색하면 됩니다.

갈 수 있는지 마는지 체크할 필요도 없이 그냥 가면 된다. 2번 3번 4번은 갈 수 있다고 해놓은 것입니다.

graph[v][i] = 1를 볼 필요 없이 1번 정점에 추가해놓은 것은 갈 수 있는 것만 추가해놓은 것입니다.

그래서 체크배열만 보면서 방문했는지만 참고하면 됩니다.

 

다시 말해서 리스트에 있는 원소 개수만 살피고, 리스트 길이만 돌면 됩니다.  이런게 리스트 방식입니다.

 

 

인접 리스트 기본 코드

ArrayList<ArrayList<Integer>>는 2차원 ArrayList를 나타내는 데이터 타입입니다. 이를 사용하여 그래프를 나타내기 위해 2차원 배열과 유사한 구조를 만듭니다. 각 정점마다 연결된 다른 정점들을 저장하는데 사용됩니다.

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

public class 인접리스트 {
    // n: 정점의 개수
    // m: 간선(Edge)의 개수  
    static int n, m, answer = 0;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();

        // 그래프를 나타내는 2차원 ArrayList 초기화
        graph = new ArrayList<ArrayList<Integer>>();

        // 그래프 초기화: 각 정점마다 ArrayList 객체 생성하여 저장
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 입력된 간선 정보를 그래프에 저장
        for (int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            // 정점 a와 연결된 정점 b를 그래프에 추가
            graph.get(a).add(b);
        }
    }
}

그래프가 아래와 같의 정의 된 경우:

n = 5
m = 4

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

그래프는 다음과 같이 표현 될 것입니다.

graph = [    [],          // 0번 정점과 연결된 정점 없음
    [2, 3],      // 1번 정점과 연결된 정점: 2, 3
    [4],         // 2번 정점과 연결된 정점: 4
    [5],         // 3번 정점과 연결된 정점: 5
    [],          // 4번 정점과 연결된 정점 없음
    []           // 5번 정점과 연결된 정점 없음
]

 

인접리스트 터미널로 출력해보기

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

public class 인접리스트 {
    // n: 정점의 개수
    // m: 간선(Edge)의 개수
    static int n, m, answer = 0;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();

        // 그래프를 나타내는 2차원 ArrayList 초기화
        graph = new ArrayList<ArrayList<Integer>>();

        // 그래프 초기화: 각 정점마다 ArrayList 객체 생성하여 저장
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 입력된 간선 정보를 그래프에 저장
        for (int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            // 정점 a와 연결된 정점 b를 그래프에 추가
            graph.get(a).add(b);
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(i + "번 정점과 연결된 정점: ");
            for (int j = 0; j < graph.get(i).size(); j++) {
                System.out.print(graph.get(i).get(j) + " ");
            }
            System.out.println(); // 줄 바꿈
        }

    }
}

// 입력
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

// 출력
1번 정점과 연결된 정점: 2 3 4 
2번 정점과 연결된 정점: 1 3 5 
3번 정점과 연결된 정점: 4 
4번 정점과 연결된 정점: 2 5 
5번 정점과 연결된 정점:

 

 

문제 강의 풀이

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

public class Main {
    static int n, m, answer=0; // 메인에서 접근할 수 있게 하기 위해 static전역변수
    // integer를 저장할 수 있는 ArrayList객체를 저장하는 ArrayList
    // 선언만했고 실제 객체 생성은 메인 메소드에서!
    static ArrayList<ArrayList<Integer>> graph;
    // 체크배열
    static int[] ch;
    public void DFS(int v) {
        if (v==n) answer ++;
        else {
            // for문 대신 for each문!
            // v의 다음 정점 = next vertex
            // v정점에서 갈 수 있는건 v번 ArrayList에 추가되어있는 상황
            for (int nv: graph.get(v)) {
                if(ch[nv]==0) {
                    ch[nv]=1; // 방문했다
                    DFS(nv);
                    ch[nv]=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 ArrayList<ArrayList<Integer>>();
        // 객체 생성하는 여기 부분 아주 중요합니다!!!
        for (int i = 0; i <= n; i++) {
            // 정수를 저장할수 있는 ArrayList객체 생성
            // 그래프는 ArrayList객체를 저장
            // add로 하니까 0번 부터 생김
            // 정점이 5개라면 6개를 생성하고 get으로 1번부터 접근
            graph.add(new ArrayList<Integer>());
        }
        ch = 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);
        }
        ch[1]= 1;
        T.DFS(1);
        System.out.println(answer);
    }
}