경로 탐색(DFS, 인접리스트, ArrayList 풀이)

경로탐색 문제

: 방향 그래프가 주어지면 1번 정점에서 N번 정점까지 가는 모든 경우의 수를 출력하는 알고리즘 짜기

2차원 배열을 이용한 풀이

문제를 풀기전 간단하게 그래프별로 행렬을 어떻게 구현하는지 살펴보자
1. 무방향 그래프

2. 방향 그래프
   

3. 가중치 그래프
   

이제 경로탐색 문제 풀이 코드를 보자면

n(정점의 개수),m(간선의 개수)를 입력받은후 for문을 이용하여 그래프의 정점과 간선을 추가한다. 시작 점인 1 정점의 check를 1로 설정한후, DFS(1)을 호출한다.

현재 정점이 n번 정점에 도달하면 answer값 증가
그 외에는 2차원 graph 배열을 돌며 graph[v][i]가 있고, 정점i가 아직 방문 전일때(ch[i]==0) i정점을 방문하고 ,DFS(i) 실행
백트래킹 후에는 방문했던 정점을 다시 방문하지 않은 상태(ch[i]==0)으로 변경

ArrayList를 이용한 풀이

메인 메서드에서 그래프 생성 및 정점과 간선 정보 입력받기