[문제풀이] 07-12. 경로 탐색(인접 리스트)

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0712. 경로 탐색(인접 리스트)

🗒️ 문제

🎈 나의 풀이

	private static int nextVertex(int[] ch, List<ArrayList<Integer>> graph, int n) {
        int way = 0;
        if(n == graph.size() - 1) return 1;

        for(int i : graph.get(n)) {
            if(ch[i] == 0) {
                ch[i] = 1;
                way += nextVertex(ch, graph, i);
                ch[i] = 0;
            }
        }

        return way;
    }
    private static int solution(List<ArrayList<Integer>> graph) {
        int[] ch = new int[graph.size()];
        ch[1] = 1;
        return nextVertex(ch, graph, 1);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<ArrayList<Integer>> graph = new ArrayList<>();

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

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

        System.out.println(solution(graph));
    }

🖍️ 강의 풀이

  	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 kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.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=kb.nextInt();
			int b=kb.nextInt();
			graph.get(a).add(b);
		}
		ch[1]=1;
		T.DFS(1);
		System.out.println(answer);
	}	

💬 짚어가기

해당 문제는 DFS와 해당 정점의 탐색 여부를 저장하는 체크 배열을 이용해 풀 수 있다.

앞서 풀이한 경로 탐색(인접 행렬) 문제와 로직은 동일하나 2차원 배열을 이용하는 경우
$n^2$ 만큼의 시간 복잡도를 요구하여, 정점의 개수가 많아지면 수행 시간이 길어진다.
따라서 이번에는 List에 간선과 방향에 대한 정보를 담고, 깊이 우선 탐색을 수행한다.

리스트 graph를 생성한다. 이 때 리스트의 요소는 정수를 리스트로 갖는 ArrayList이다.
간선의 시작 정점의 번호를 graph 리스트의 인덱스로하고, 가르키는 정점의 번호를 해당
리스트에 추가한다.

이제 방문한 정점에 대한 정보를 ch[] 배열에 보관하며, DFS를 수행하여 문제를 해결한다.