[알고리즘/java] 경로탐색(DFS 인접리스트, ArrayList)

[알고리즘/java] 경로탐색(DFS 인접리스트, ArrayList)

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

- https://inf.run/Azjw

문제 : 방향그래프가 주어지면 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

저번 게시글 2021.12.21 - [분류 전체보기] - [알고리즘/java] 경로탐색(DFS) 에서는 위 문제를 인접행렬(2차원배열)로 풀었지만, 문제에서 정점의 수가 20이 아닌 100, 1000, 그 이상 커지게 되면 인접행렬로 탐색하는 방법은 굉장히 비효율적이다.

정점의 수가 1000이라면 배열 크기만 해도 1000 * 1000에, 한 정점을 탐색하기 위해 1000번의 for문을 돌고 모든 정점을 탐색하려면 거기에 또 *1000을 해야하기 때문이다.

그러므로 정점의 수가 클 때는 경로탐색 문제를 인접리스트 를 이용하여 푼다.

위의 그림은 입력 예시인

5(n) 9(m)

1 2

1 3

1 4

2 1

2 3

2 5

3 4

4 2

4 5

의 순서대로 각 정점에 인접리스트를 만들어 연결된 정점을 추가시켜 준 그림이다.

1부터 N까지 가는 방법의 가지 수를 구하는 코드는 전체적 로직은 인접행렬로 구현하는 방법과 크게 다르지 않다.

하지만 인접행렬은 정점마다 정점의 개수만큼 for문을 돌려 연결된 정점을 찾아야하는 것과 달리,

인접리스트는 이미 정점마다 리스트에 연결된 정점을 추가해 놓았기 때문에 방문했는지 여부를 체크하는 배열만 확인하면 된다.

< 경로탐색 인접리스트 전체 코드 >

public class Main { private static int n, m, answer = 0; private static ArrayList> graph; private static int[] ch; public static 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) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); n = scan.nextInt(); m = scan.nextInt(); graph = new ArrayList>(); ch = new int[n + 1]; for (int i = 0; i <= n; i++) { graph.add(new ArrayList()); } // 그래프 인접리스트로 만들기 for (int i = 0; i < m; i++) { int a = scan.nextInt(); int b = scan.nextInt(); graph.get(a).add(b); } ch[1] = 1; DFS(1); System.out.println(answer); } }

< 세부 풀이 >

private static ArrayList> graph; graph = new ArrayList>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList()); } // 그래프 인접리스트로 만들기 for (int i = 0; i < m; i++) { int a = scan.nextInt(); int b = scan.nextInt(); graph.get(a).add(b); }

: 1~n까지의 정점의 리스트, 또 그 안의 각 정점에 연결된 노드를 추가하기 위한 리스트를 생성한다.

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

: 각 정점에 리스트(graph.get(v))에 대해 for-each문을 돌려 방문하지 않은 정점에 대한 DFS를 실행한다.

from http://bumbleb22.tistory.com/14 by ccl(A) rewrite - 2021-12-22 05:01:58