12. 경로탐색 (DFS)

1. 문제

 

1번 정점에서 5번 정점으로 가는 모든 경로의 수를 출력하는 프로그램을 작성하시오.

이미 지난 정점은 다시 지날 수 없다. (1번 정점도 포함)

1번 정점에서 5번 정점으로 가는 가짓수는 6가지로 아래와 같다.

1 2 3 5 6

1 2 5

1 3 4 2 5

1 3 4 5

1 4 2 5

1 4 5

 

 

2 - 1. 나의 풀이

일단 DFS로 푸는 건 알았다.

그림을 그려보면서 손코딩으로 대충 짜보고 실제로 코드 넣으면서 문제를 풀었다.

 

일단 DFS(int vertex)가 실행될 때

graph[vertex][edge] == 1 이면 DFS(edge)인 재귀함수를 호출해서 꼬리에 꼬리를 무는 방식으로 풀면 된다는 감을 잡았다.

 

문제는 지나간 정점을 다시 지나지 않기 위함이다.

자연스럽게 체크배열을 설정했다.

체크배열은 값이 1이면 지나갔다는 뜻, 0이면 아직 지나가지 않았다는 뜻이다.

DFS(edge)를 호출하기전에 ch[edge]=1;로 고치고 해당 재귀함수로 들어간다.

 

여기서 또 문제는 재귀함수가 return 될 때 다시 체크배열을 0으로 원상복구하는 방법이다.

이걸 가장 많이 고민했는데 방법은 간단했다.

DFS(edge); 아래 코드에 ch[edge]=0;을 쓰면된다. (스택 프레임의 흐름을 알아야하는 이유)

{ //재귀 함수의 일부
ch[edge] = 1;
DFS(edge);
ch[edge] = 0;
}

재귀함수에 들어가기전에 체크배열로 지나갔다는 표현을하고 재귀가 끝나면 다시 되돌아 왔다는 표현을 하는것이다.

 

★for(int i = 2 ; ...)에서 i = 1로 고친 다음 ch[1] = 1;로 기본으로 초기화해도 된다.

 

2 - 2. 나의 코드

package BFS_DFS;
import java.util.*;

public class dfs12 {
    static int[][] graph;
    static int count =0;
    static int[] ch; //해당 엣지로 들어갈 때 해당 엣지가 1이면 이미 사용했다는 뜻

    public static void DFS(int vertex, int n) {
		//if(vertex == 5 ){ count++; return; } 5번 정점임을 여기서 확인해도 된다.
        for (int edge = 2; edge <= n; edge++) { //1번 정점은 맨처음에 사용하므로.
            if(graph[vertex][edge] == 1 && ch[edge] ==0){
                if(edge==5){
                    count++;
                    return;
                }else{
                    ch[edge]=1; //이 엣지를 사용했다는 뜻
                    DFS(edge, n);
                    //DFS가 끝나서 스택프레임이 사라질 때 이 아래칸에 ch[edge]=0해주는게 포인트!!!
                    ch[edge]=0;
                }
            }
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        graph = new int[n+1][n+1];
        ch = new int[n + 1]; //체크배열 기본 0

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

        DFS(1, n);
        System.out.print(count);
/*
        //graph 인접 행렬 확인용
        for (int[] a : graph) {
            for (int x : a) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
*/
    }
}

 

3. 강의

나와 같다.

 

 

4. 얻어갈 점

DFS가 끝났을 때, back 했을 때의 상황도 고려하자