개발하는지호

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

by 개발하는지호

코딩테스트

<<풀이>>

 

이번에는 ArrayList를 활용해서 경로 탐색을 풀어보았다.

 

이는 기존에 2차 배열을 ArrayList로 변형 시켜서 구한 것인데,

 

ArrayList 내부에 또다른 ArrayList를 넣는 방법을 사용했다.

 

기존에는 인접하는 것이 있다면 2차배열에 1을 추가해줬지만 

 

컬렉션 프레임워크에 속하는 ArrayList를 사용하면 2차 배열을 사용하지 않고, 각 값이 인접하는 데이터를 넣을 수 있다.

 

 

import java.util.ArrayList;
import java.util.Scanner;
 
class Main {
    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) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        ch = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            graph.get(a).add(b);
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}

 

*ArrayList 안에 ArrayList를 넣을 수 있다니 놀랍다 ㅋㅋ

블로그의 프로필 사진

블로그의 정보

DevSecOps

개발하는지호

활동하기

티스토리툴바