[문제풀이] 07-11. 경로 탐색(인접 행렬)

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

Recursive, Tree, Graph - 0711. 경로 탐색(인접 행렬)

🗒️ 문제

🎈 나의 풀이

	private static int nextVertex(int[] ch, int[][]graph, int n) {
        int way = 0;
        if(n == graph.length-1) return 1;

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

        return way;
    }
    private static int solution(int[][] graph) {
        int answer = 0;
        int[] ch = new int[graph.length];
        ch[1] = 1;

        answer+= nextVertex(ch, graph, 1);

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] graph = new int[n + 1][n + 1];

        for(int i=0; i<m; i++) {
            graph[sc.nextInt()][sc.nextInt()] = 1;
        }

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

🖍️ 강의 풀이

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

💬 짚어가기

해당 문제는 DFS와 해당 정점의 탐색 여부를 저장하는 체크 배열을 이용해 풀 수 있다.
2차원 배열에 간선과 방향에 대한 정보를 담고, 깊이 우선 탐색을 수행한다.

이 때 이미 방문한 정점을 또 방문하게 될 때 무한 루프가 발생 할 수 있다. 따라서 해당
노드에 방문할 시 ch[] 배열에 노드의 번호에 해당하는 인덱스 요소에 1을 보관한다.

그후 목적 노드에 도착할 때 마다 카운트하여 문제를 해결 할 수 있다.