문제
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. (한번 방문한 노드는 다시 방문할 수 없습니다)
위 그래프에서 1번 정점에서 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
총 6 가지입니다.
▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.
▣ 출력설명
총 가지수를 출력한다.
▣ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
▣ 출력예제 1
6
풀이
사실 인접행렬 방법은 정점 개수가 많아지면 메모리 낭비도 되고 시간 복잡도도 길어진다.
N이 10000 이라고 하면, 이차원 배열의 크기가 10000 x 10000 만큼 필요하다.
그리고 1번 정점 부터 갈 수 있는 정점을 살필 때 1부터 10000까지 돌아야한다.
이럴 때는, 'Integer를 원소로 갖는 ArrayList' 를 원소로 갖는 인접 리스트(ArrayList)를 선언하고,
정점 i - i번 리스트로 매칭한다. 예를 들어 1번 정점이 갈 수 있는 정점은 1번 리스트에 순서대로 추가하는 것이다.
따라서 정점을 탐색할 때 리스트 사이즈까지만 돌면되어서 훨씬 효율적이다.
(※ 인덱스는 0 부터 시작함, 0번 리스트는 버림)
1번 정점 - 1번 리스트
2 | 3 | 4 |
2번 정점 - 2번 리스트
1 | 3 |
3번 정점 - 3번 리스트
4 |
4번 정점 - 4번 리스트
2 | 5 |
5번 정점 - 5번 리스트
X
코드
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int n, m, answer = 0;
static ArrayList<ArrayList<Integer>> graph; //integer를 저장할 수 있는 ArrayList를 저장하는 ArrayList
static int[] ch; //방문한 적이 있으면 값이 1
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) {
Scanner in = new Scanner(System.in);
n = in.nextInt();//정점의 수 1~20
m = in.nextInt(); //간선의 수
graph = new ArrayList<ArrayList<Integer>>(); //인덱스 번호 = 정점 번호 1~n번
ch = new int[n+1];
for(int i=0; i<=n; i++) { //정점의 개수 +1 만큼 ArrayList 추가(0번 리스트는 버림)
graph.add(new ArrayList<Integer>()); //0번 인덱스 부터 시작된다
}
for(int i=0; i<m; i++) {
int a = in.nextInt();
int b = in.nextInt();
graph.get(a).add(b);
}
ch[1] = 1; //1부터 시작
DFS(1);
System.out.println(answer);
}
}
'PS(Java) > 인프런 강의 문제' 카테고리의 다른 글
[PS] 인프런 강의 - DFS 1. 합이 같은 부분집합(아마존 인터뷰) (0) | 2022.09.27 |
---|---|
[PS] 인프런 강의 - Graph 4. 그래프 최단거리(BFS) (0) | 2022.09.26 |
[PS] 인프런 강의 - Graph 2. 경로 탐색(인접 행렬) (0) | 2022.09.26 |
[PS] 인프런 강의 - Graph 1. 그래프와 인접행렬 (0) | 2022.09.25 |
[PS] 인프런 강의 - Tree 5. Tree 말단 노드까지의 가장 짧은 경로 (0) | 2022.09.25 |