[알고리즘/java] 경로탐색(DFS 인접행렬, 2차원 배열)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

문제 : 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하라.

 

위 그래프에서 1에서 N(=5)까지 가는 방법의 가지 수는 다음과 같다.

 

1 2 3 4 5

1 2 5 

1 3 4 2 5

1 3 4 5 

1 4 2 5

1 4 5

 

입력 예시 :

5(n) 9(m)
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

 

---

이 문제는 방향그래프는 인접행렬로 표현하고 가지 수를 구하는 방법은 DFS로 구현한다.

여기서 1에서 N으로 갈 때 방문한 노드는 다시 방문하지 않도록 체크해주는 것이 중요하다.

 

아래 그림은 1에서 N으로 가는 DFS를 D(V)로 표현하여 가지 수를 찾는 과정 중 일부이다.

 

D(1) : 

1에서 출발하기 때문에 check 배열에 1을 방문했음을 먼저 표시하고, 

for문을 N번(정점의 개수)을 돌려 1에서 갈 수 있는 노드를 찾으면 먼저 2를 방문하게 된다.

 

D(2) :

check배열에 2를 방문했음을 먼저 표시하고,

for문을 N번(정점의 개수)을 돌려 2에서 갈 수 있는 노드를 찾으면 먼저 3를 방문하게 된다.

 

D(3) :

check배열에 3를 방문했음을 먼저 표시하고,

for문을 N번(정점의 개수)을 돌려 3에서 갈 수 있는 노드를 찾으면 먼저 4를 방문하게 된다.

 

D(4) :

check배열에 4를 방문했음을 먼저 표시하고,

for문을 N번(정점의 개수)을 돌려 4에서 이미 방문한 노드를 제외하고 갈 수 있는 노드를 찾으면 5를 방문하게 된다.

 

D(5) :

V == N이기 때문에 dfs를 종료하여 첫 번째 루트인 ' 1 2 3 4 5 ' 를 찾아 가지 수+1을 해준다.

 

 

그리고 다른 가지 수를 찾기 위하여 다시 back할 때에는 check배열에 방문하지 않음으로 표시한다.

 

 

 

 

< 경로탐색(DFS) 전체코드 >

public class Main {

	private static int n, m, answer = 0;
	private static int[][] graph;
	private static int[] ch;

	public static 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) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		graph = new int[n + 1][n + 1];
		ch = new int[n + 1];

		// 그래프 인접행렬로 만들기
		for (int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			graph[a][b] = 1;
		}

		ch[1] = 1;
		DFS(1);

		System.out.println(answer);

	}

}

 

< 세부 풀이 >

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

: 서로 연결된 두 개의 정점을 m번 만큼 받아 그래프에 저장한다.

  방향 그래프이기 때문에 행(a)이 열(b)로 간다고 생각. ( a 정점이 b정점으로 간다)

 

 

		ch[1] = 1;
		DFS(1);

: 1번부터 DFS를 시작하기 때문에 시작하기 전 체크배열 ch에 1번 노드를 방문했음을 표시한다.

 

public static 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;
				}
			}
		}

	}

: 각 정점을 기준으로 1부터 정점의 개수 n만큼의 for문을 돌면서, 

해당 노드에서 다른 노드로 갈 수 있는지와 방문하지 않은 노드인지 여부를 확인한다. 

(      if (graph[v][i] == 1 && ch[i] == 0)     )

그리고 조건을 만족하는 노드를 방문했다고 표시하고 DFS(해당노드)를 실행한다.

 

ch[i]=0을 해주는 부분은 dfs가 끝났을 때 노드를 다시 방문할 수 있게 돌려 놓는 것이다.