문제
- 방향 그래프가 주어지면 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. 정점 노드로 가는 하나의 방법이 완성되었으면, 정점 노드에서 하나씩 뒤로 가면서 다음으로 연결되는 방법을 찾는다.
5. 이 때, 기존에 방문했던 노드는 방문하지 않았다는 값으로 변경해준다.
풀이과정
1. 전역으로 각 변수들을 선언하고 일부 값들을 입력받는다.
- N : 노드의 개수를 의미한다.
- M : 간선의 개수를 의미한다.
- result : N까지 가는 경우의 수를 의미한다.
- graph[ ][ ] : 2차원 배열의 행과 열은 각각의 정점 번호를 의미한다.
- ch[ ] : 방문 여부를 확인할 값이 들어있는 배열이다.
2. 2차원 배열을 입력받을 때, graph[A][B]에 1을 넣는다.
- 방향 그래프이며 A에서 B로 간다는 의미이다.
- 즉, A -> B 를 의미한다.
3. ch 배열의 첫번째에 1을 넣는다.
- 맨 처음에 자신의 노드는 방문을 반드시 해야하기 때문이다.
- 처음이 0이 아닌 이유는, 1번 ~ N번 까지의 정점 노드를 구하기 위해 N+1 까지로 배열의 크기를 잡았기 때문이다.
4. DFS 메소드 구현으로 넘어가보자.
5. 정점 노드에 도달하면 그대로 결과를 출력한다.
6. 정점 노드가 아니라면 graph[v][i] 가 1 이고, ch[i] 가 0 일 경우에 ch[i]에 1을 넣는다.
- graph[v][i] 를 통해 입력받은 v행에서 i~N번째 열을 확인한다. 이 값이 1이라면 갈 수 있다는 의미이다.
- ch[i] == 0 이라는 것은 방문 하지 않았음을 의미한다.
7. 해당 노드에 대해 방문 여부를 확인했으면, DFS() 를 다시 호출하여 다음 노드를 확인한다.
- 현재 입력받은 행에 대한 경로는 확인이 끝났으니 다음 행을 찾기 위해 i로 변경하여 작업한다.
8. DFS()를 다시 호출한 후에는 ch[i] 에 값을 다시 0으로 변경한다.
- 호출 한 후에 뒤로 돌아갈 때에는 방문하지 않았다는 0을 넣어서 다음 탐색을 한다.
9. 아래에서 이미지와 함께 자세히 이해해보자.
[ 방향 그래프 (1 -> 2) ]
1. graph[1][1] 에는 1이 들어가있다. 이를 통해 DFS(1) 을 호출했을 때, if(graph[v][i] == 1 && ch[i] == 0) 에 걸리게 된다.
2. 그러나 ch[1] 에 1이 들어가있기에 if 문에 충족되지 못하고, 밖으로 나와서 DFS(2)를 호출하게 된다.
3. DFS(2)를 호출하면 grahp[1][2]가 되고, 위에 적힌 두 개의 if 조건을 충족하기에 방문했다는 의미로 ch[2] 에 1이 들어간다.
(아래 그림은 해당 과정까지를 2차원배열, 트리, 방향 그래프로 각각 표현한 내용이다.)
[ 방향 그래프 (2 -> 3) ]
4. 2부터 연결되는 노드를 찾아야하므로 DFS(i) 를 통해 graph[2][ ] 에 대해 탐색을 시작한다.
5. graph[2][3] 이 if문의 두 조건을 충족하므로 ch[3] 에 1이 들어간다.
[ 방향 그래프 (3 -> 4) ]
6. 3부터 연결되는 노드를 찾아야하므로 DFS(i) 를 통해 graph[3][ ] 에 대해 탐색을 시작한다.
7. graph[3][4] 이 if문의 두 조건을 충족하므로 ch[4] 에 1이 들어간다.
[ 방향 그래프 (4 -> 5) ]
8. 4부터 연결되는 노드를 찾아야하므로 DFS(i) 를 통해 graph[4][ ] 에 대해 탐색을 시작한다.
9. graph[4][5] 이 if문의 두 조건을 충족하므로 ch[5] 에 1이 들어간다.
[ 방향 그래프 (2 -> 5) ]
10. 정점 노드에 도달했으므로 하나씩 뒤로 이동하며 재탐색한다.
11. 먼저 5에서 빠져나와야 하기에 방문하지 않았다는 것을 나타내기 위해 ch[5] 값을 0으로 변경한다.
12. 빠져나온 후에 연결되는 노드를 찾아야하므로 DFS(i) 를 통해 탐색한다.
13. 위 과정에서는 2까지 돌아와야 연결되는 노드가 있으므로 graph[2][5] 를 통해 ch[5]에 1을 넣는다.
(이 때, 2차원 배열은 그래프의 간선 여부 즉, 연결되어 있으면 1을 넣는 것이기에 아래 그림처럼 되지만
방문 여부를 확인하는 ch[] 배열은 계속해서 값이 변하는 것이기에 양방향 그래프에 색이 칠해진 것이 1이라고 보면 된다.)
10. 위 과정을 반복하며 결과값을 출력한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
