자바(Java) 알고리즘 문제풀이 인접행렬 경로탐색 [인프런 / 모든 조합 유형]

출처) 인프런

강의의 문제를 가져왔기 때문에 밝힙니다 ! 
임의로 추가, 수정, 삭제한 내용들이 있으니 정확한 이해를 위해서는 강의를 구매하시는 것을 추천드립니다 😅
출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 (인프런 강의) 

 

---

 

 

풀이 코드

인접 행렬로 그래프를 표현해서 풀이하는 방법과 인접 리스트로 그래프를 표현해 풀이하는 방법이 있다.

먼저 인접 행렬로 풀이하자면, 2차원 배열을 만들고 간선의 갯수만큼 반복문을 설정한 뒤 A 노드와 B 노드가 연결되어있다고 가정했을 때

matrix[a][b] = 1 로 배열을 채워주면 된다. 그러고 행을 기준으로 잡고 1로 표시되어 있는 열을 찾으면 되는데 즉, 서로 연결되어있는

노드를 찾아주는 것을 의미한다. 예를 들어, matrix[1][2] = 1 이라면 1번 노드와 2번 노드가 서로 연결되어있다는 것.

 

이 문제는 모든 경로의 가짓수를 출력하는 문제이므로 정점 노드까지 도달했을 때 가짓수를 하나씩 증가하는 방향으로 분기문을 걸어주면 되고, 그게 아니라면 현재 위치한 노드(행) 에서 연결된 노드(열) 이 연결되어 있는지(1인지?), 그리고 방문 표시가 되어있지 않는지 ? 확인하고 방문이 되지 않았다면 연결된 노드(열) 을 방문했다고 표시하기 위해 1로 바꿔준 뒤 해당 노드를 다시 출발 노드로 해서 DFS 재귀 호출을 하면 된다. 이 때 주의할 점으로 DFS 재귀 호출 아래부분에 방문 표시를 풀어주는 코드를 작성해줘야한다. 이렇지 않으면 스택 특성 상

작업이 끝나고 다시 돌아올 때, 연결된 노드에 방문 표시가 없어지지 않았으므로 제대로 된 판단을 할 수 없기 때문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 모든 경로의 가짓수를 출력하는 문제 (인접 행렬)
// 모든 배열은 +1 의 길이를 가지도록 설정한다. 노드가 1번부터 시작하니까 맞춰주기 위함
public class AdjacencyMatrix {
    static int answer = 0;
    static int nodeIdx;
    static int edge;
    static int[] checkArr;
    static int[][] matrix;

    // v = 출발 노드번호
    public static void DFS(int v) {
        if (v == nodeIdx) {
            answer++;
        } else {
            for (int i = 1; i <= nodeIdx; i++) {
                if (matrix[v][i] == 1 && checkArr[i] == 0) {
                    checkArr[i] = 1;
                    DFS(i);
                    checkArr[i] = 0; // 다시 돌아올 때 꼭 체크를 풀어줘야한다.
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeIdx = Integer.parseInt(st.nextToken()); // 노드 번호
        edge = Integer.parseInt(st.nextToken()); // 간선 갯수
        checkArr = new int[nodeIdx + 1]; // 방문체크 배열
        matrix = new int[nodeIdx + 1][nodeIdx + 1]; // 인접행렬 그래프

        for (int i = 0; i < edge; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());
            matrix[a][b] = 1;
        }
        checkArr[1] = 1;
        DFS(1); // 1번 노드부터 출발
        System.out.println(answer);
    }
}