자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Graph/DFS_경로탐색_인접행렬)

 

12. 경로탐색(DFS)

 

예시 입력 1 

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

예시 출력 1

6

 

인접행렬 기본 코드

인접 행렬(Adjacency Matrix)은 그래프의 연결 정보를 행렬로 표현하는 방법입니다. 정점 간의 연결 여부를 2차원 배열로 나타내며, 두 정점이 연결되어 있으면 1로 표시하고 연결되어 있지 않으면 0으로 표시합니다.

import java.util.Scanner;

public class 인접행렬 {
    // n: 정점의 개수
    // m: 간선(Edge)의 개수
    static int n, m, answer=0;
    static int[][] graph;
    public void DFS(int v) {

    }
    public static void main(String[] args) {
        인접행렬 T = new 인접행렬();
        Scanner kb = new Scanner(System.in);
        // 정점의 개수와 간선의 개수 입력
        n=kb.nextInt();
        m=kb.nextInt();
        // 인접 행렬 초기화
        graph=new int[n+1][n+1];

        // 간선 정보 입력
        for (int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            // 정점 a와 b를 연결한다면 1로 표시 (무방향 그래프일 경우 양방향으로 표시)
            graph[a][b] = 1;
//            graph[b][a] = 1; // 무방향 그래프의 경우
        }
        // 인접 행렬 출력
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println(); // 줄 바꿈
        }

    }
}

 

// 입력
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
// 출력
0 1 1 1 0 
1 0 1 0 1 
0 0 0 1 0 
0 1 0 0 1 
0 0 0 0 0

방향그래프를 인접행렬로 표현하고, 1번 정점에서 m번 정점으로 가는 가지 수를 출력하라

그래프 이론에서 경로라는 것은 중복된 노드가 없어야 합니다. 한번 방문한 노드는 다시 방문하면 안됩니다.

 

처음에는 DFS()재귀함수에 1번 노드가 매개변수로 넘어가게 됩니다. 1번 정점에서 출발 합니다.

재귀 함수는 항상 자기가 방문한 노드를 재방문하지 않기 위해 체크해야 합니다.

 

1. for문 i가 노드, 정점이 번호가 됩니다. for문을 순회하면서 재귀호출을 n가닥 뽑아냅니다.
2. i가 1일때 자기 자신은 방문 안해도 되니까 넘어갑니다.
3. i가 2일때 아직 방문 안했고, 갈수도 있습니다. 그래서 체크배열을 체크하고 DFS(2)로 넘어가게 됩니다.
4. 그러면 DFS(2)도 for문을 돌면서 i가 1일때, 1로 갈 수는 있지만, 체크 되어있어서 안갑니다.
5. 2번 노드에서 자기자신제외하고 3번부터 갈 수있는지 체크하고 DFS(3)을 호출합니다.
6. 3번 정점에서 또 for문을 돌면서 1번과 2번은 갈수도 없고 체크도 되어있습니다. 자기자신은 못가고,
7. 4번 노드는 갈수 있으니 체크하고 DFS(4)를 호출합니다. 마찬가지로 for문을 돌면서 DFS(5)로 갈 수 있는걸 확인합니다.
8. if else로 분기처리해주고 v가 n일때 카운팅해줍니다. back해줄때 체크된걸 풀어줘야합니다.

문제 강의 코드

import java.util.Scanner;

// 그래프
public class Main {
    static int n, m, answer=0; // 메인에서 접근할 수 있게 하기 위해 static전역변수
    static int[][] graph;
    static int[] ch;
    public void DFS(int v) {
        if(v==n) answer++;
        else {
            for (int i = 1; i <= n; i++) {
                // v번 행에서 갈 수 있는 열을 찾아라(인접행렬)
                // 체크가 안되어있는 거 찾아라
                if(graph[v][i] == 1 && ch[i] == 0) {
                    ch[i] = 1;
                    DFS(i); // 18라인
                    ch[i] = 0; // 호출 밑에서는 back해서 이 지점으로 오니까 체크 풀어주기
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt(); // 노드 개수
        m=kb.nextInt(); // 간선 개수
        graph=new int[n+1][n+1]; // 1번 인덱스부터 n번 인덱스까지 정점 번호가 나와야 해서 +1
        ch=new int[n+1]; // 1번 부터 n번가지 있어야 하므로
        for (int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph[a][b] = 1; // a에서 b로 간다
        }
        ch[1] = 1; // 1번 노드는 출발점이라 체크
        T.DFS(1); // 출발점 1번
        System.out.println(answer);
    }
}

 

상태 트리 그리면서 이해하기

 

스택 프레임 그리면서 이해하기