그래프, 경로탐색, 인접리스트

🔑 인접리스트 키워드

정점(노드)이 10000개, 100000개 등으로 엄청 많을 때
인접행렬로 풀기(10000 * 10000개)에는 노드 수가 너무 많을 떄
노드 수가 너무 많아져버리면 인접 행렬로 풀기에는 시간 복잡도⬆️, 잡아먹는 메모리⬆️

✅ 인접리스트로 1번 노드부터 5번 노드까지 갈 수 있는 경우 가지 수 구하기

✔️ input & output

앞전 문제랑 똑같음

5 9 //정점 노드 수, 간선 수
1 2 //여기서부터 연결 정보
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

//output: 6

✔️ psvm

• 앞선 문제와 마찬가지로 n, m, answer, ch[], graph<>모두 static으로, class에서 선언되었다.
• ch[]는 n+1만큼 크기 만들고
• graph<>는 ArrayList<>를 요소로 가지는 ArrayList<>이다.
• 먼저 graph<>의 ArrayList<>는 n+1개를 만들어야 한다. 물론 그래프의 0번 인덱스는 쓰이지 않겠지만, 나중에 get을 하기 위해서 필요하다. get을 할 때는 인덱스로 ArrayList의 요소들을 가져오기 때문에 0부터 시작해야 하기 때문이다.

graph[0]: []          # Vertex 0 (unused)
graph[1]: [2, 3, 4]      # Vertex 1 is connected to 2 and 3, 4
graph[2]: [1, 3, 5]         # Vertex 2 is connected to 1, 3, 5
graph[3]: [4]
graph[4]: [2, 5]
graph[5]:         # Vertex 5 has no neighbors

✔️ DFS 함수

• v번째 인덱스의 ArrayList를 cur로 가져옴.
• 예를 들어 DFS(1)의 cur은 graph[1]: [2, 3, 4] 이렇게 생겼을 것이다.
• 이제 이 v가 우리가 가고자 하는 노드(이 문제의 경우에는 n)인지 확인하고 맞으면 answer++
• 아니면 이 노드에 갔었는지 ch배열 확인
• 안 갔으면 갔다고 체크하고 ch[x]=1 간 다음,
• 되돌아올때는 안 갔다고 다시 체크 ch[x]=0

🟢 CODE

class Main {
    static int n;
    static int m;

    static int ch[]; //체크배열

    static ArrayList<ArrayList<Integer>> graph;
    static int answer; //재귀 함수에 초기화되지 않기 위해서 static


    public void DFS(int v) {
        ArrayList<Integer> cur= graph.get(v);
        if(v==n) answer++;
        else{
            for(int x: cur){
                if(ch[x] != 1){
                    ch[x]=1;
                    DFS(x);
                    ch[x]=0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T= new Main();
        Scanner sc= new Scanner(System.in);
        n= sc.nextInt();
        m= sc.nextInt();
        ch= new int[n+1];
        graph= new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>()); //arrayList를 n개 만들기
        }
        for(int j=0; j<m; j++){
            int a= sc.nextInt();
            int b= sc.nextInt();
            graph.get(a).add(b); //a번 리스트에 접근해서 b를 추가
        }
        ch[1]=1;
        T.DFS(1);
        System.out.print(answer);
    }
}

⭐️ 주의!

    ch[1]=1;
    T.DFS(1); //⭕️

    T.DFS(1);
    ch[1]=1; //❌

이 순서가 바뀌면 안된다.
먼저 ch배열에 1 방문했다고 체크를 하고, DFS(1)을 돌아야 한다.
만약 DFS(1)을 돌고 ch배열을 체크하면 답이 다르게 나온다.