섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 13. 경로탐색(인접리스트, ArrayList)

문제

• 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.
• 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는
• 1 2 3 4 5
• 1 2 5
• 1 3 4 2 5
• 1 3 4 5
• 1 4 5
• 총 6 가지입니다. 

입력

• 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.
• 그 다음부터 M 줄에 걸쳐 연결정보가 주어진다.

출력

• 총 가지수를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 이진트리, 재귀함수를(을) 사용하여 푸는 문제이다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

설계과정

1. 각 노드별로 연결 가능한 노드들을 리스트로 저장한다.

2. 해당 노드를 방문하지 않았다면 방문했다는 값을 넣어준다.

3. 정점 노드로 가는 하나의 방법이 완성되었으면 기존에 방문했던 노드는 방문하지 않았다는 값으로 변경해준다.

4. 리스트에 저장된 노드들을 비교하여 연결 가능한지 확인한다.

---

풀이과정

1. 전역으로 각 변수들을 선언하고 일부 값들을 입력받는다.

• N : 노드의 개수를 의미한다.
• M : 간선의 개수를 의미한다.
• result : N까지 가는 경우의 수를 의미한다.
• graph[ ][ ] : 연결 정보를 저장한다. (연결이 가능한 노드들을 저장한다.)
• 여기서 graph는 ArrayList<Integer> 를 저장할 수 있는 객체를 저장하는 ArrayList로 선언한다.
• ch[ ] : 방문 여부를 확인할 값이 들어있는 배열이다.

2. 2차원 배열을 입력받을 때, graph에서 A 값을 가져온 후에 그 뒤에 B 값을 더해서 넣는다.

 

3. ch 배열의 첫번째에 1을 넣는다.

• 맨 처음에 자신의 노드는 방문을 반드시 해야하기 때문이다.
• 처음이 0이 아닌 이유는, 1번 ~ N번 까지의 정점 노드를 구하기 위해 N+1 까지로 배열의 크기를 잡았기 때문이다.

4. DFS 메소드 구현으로 넘어가보자.

 

5. 정점 노드에 도달하면 그대로 결과를 출력한다.

 

6. v번 ArrayList와 nv를 하나씩 대응하여 방문 여부를 확인한다.

• ch[nv] == 0 이라는 것은 방문 하지 않았음을 의미한다.

7. 해당 노드에 대해 방문 여부를 확인했으면, DFS() 를 다시 호출하여 다음 노드를 확인한다.

 

8. DFS()를 다시 호출한 후에는 ch[nv] 에 값을 다시 0으로 변경한다.

• 호출 한 후에 뒤로 돌아갈 때에는 방문하지 않았다는 0을 넣어서 다음 탐색을 한다.

아래 글과 비교하며 이해해보자.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 12. 경로탐색(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 12. 경로탐색(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.