Java 그래프 문제 -인접 행렬, 인접 리스트 ,DFS, BFS

개요 목적

이번 시간에는 코딩 테스트 그래프 문제를 풀기 위한

그래프 인접 행렬 인접 리스트 표현 문제 풀이 방식에 대해서 알아본다.

DFS, BFS 방식의 그래프 문제들을 풀어보면서 심화 그래프 문제 풀이 방법도 알아보자.

그래프와 인접 행렬

무방향 그래프, 방향 그래프, 가중치 방향 그래프를 컴퓨터가 이해할 수 있는 인접 행렬로 표현을 해보자.

1. 무방향 그래프

무방향 그래프는 양방향 그래프라고도 한다.

해당 그래프가 이루어진 노드와 엣지(간선)의 숫자 집합을 나열해보면,

1 2

1 3

2 4

2 5

3 4

3 1

4 2

5 2

이 들어온 수를 grab[a][b] = 1 grap[b][a]로 체크를 하면 인접 행렬을 구할 수 있다.

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

1번 정점과 연결된 곳은 2번과 3번 이라고, 인접 행렬을 보고 그래프 모양을 추측 할 수 있다.

같은 방식으로, 방향 그래프와 가중치 그래프를 인접 행렬로 표시할 수 있다.

2. 방향 그래프

방향 그래프는 grap[a][b]=1로만 처리하고 역 방향인 grap[b][a]는 1로 체크하지 않는다.

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

3. 가중치 그래프

grap[a][b] 값을 입력할 때 1이 아닌 가중치 값을 입력해서 인접 행렬로 표현할 수 있다.

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

그래프 DFS BFS 활용 문제 

1. 경로 탐색(인접 행렬)-DFS

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

풀이

DFS(1) 부터 시작해서

graph[1] (1과 연결된 노드)로 DFS() 재귀 함수를 호출한다. 그리고 ch[1] =1 로 변경해서, 노드 1로부터 뻗어 나간, 노드 DFS()들은 1을 다시 거치지 않게 설정한다.

그리고 자식 DFS() 가 끝나면 ch[1] = 0 처리를 해서 마무리한다.(DFS(1)은 제외 항상 포함된다) → DFS(2)의 경우 DFS(3)으로 가기 전에 ch[2] =1 처리를 하고, DFS(3)이 끝나면 ch[2] =0 처리를 통해 갔다는 표식을 지운다. 그렇게 해야지만, DFS(1) → DFS(3) → DFS(4) 에서 DFS(2)를 호출해서 올바른 값을 구할 수 있다.

import java.util.Scanner;

public class 경로탐색DFS {

    static int n, m, answer=0;
    static int[][] graph;
    static int[] ch;

    public static void DFS(int v) {
        if(v==n) answer++;
        else{
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1 && ch[i]==0){
                    ch[i]=1;
                    DFS(i);
                    ch[i]=0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        graph=new int[n+1][n+1];
        ch=new int[n+1];
        for(int i=0; i<m; i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            graph[a][b]=1;
        }
        ch[1]=1;
        DFS(1);
        System.out.println(answer);
    }
}

2 경로 탐색(인접 리스트)-DFS 이용

위 문제와 같은 내용을 이번에는 인접 행렬이 아닌 인접 리스트를 사용해서 풀어보자.

인접 행렬의 경우 노드 접점이 1000개만 되어도 DFS안에서 이중 for문을 돌기 때문에, 풀이가 1초를 초과한다.

노드 접점이 많아도 시간이 짧게 걸리는 인접 리스트로 그래프를 표현해서 빨리 풀 수 있다.

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

풀이

그래프를 인접 리스트로 표현하면 아래 그림과 같다.

인접 리스트 인덱스 리스트가 노드가 되고, 인덱스 리스트 안에 있는 Integer들이 노드에서 갈 수 있는 접점들이다.

import java.util.ArrayList;
import java.util.Scanner;

public class 그래프인접리스트 {
    static int n, m , answer = 0;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;

    static void DFS(int v) {
        if (v == n) {
            answer++;
        } else {
            for (Integer nv : graph.get(v)) {
                //DFS(1)을 예를 들면 graph.get(1) = 1에 갈수 있는 노드 nv = 2,3,4 이다.
                if (ch[nv] == 0) {
                    //가려고 하는 접점이 0이라면, 거치지 않았던 곳이라면,
                    //갔다는 표시를 하고
                    ch[nv] = 1;
                    //해당 접정을 DFS 실행
                    DFS(nv);
                    //끝나면 거쳤다는 표시를 삭제
                    ch[nv] = 0;

                    //그리고 다시 DFS(1) 에서 갈 수 있는 접점 nv => 3을 실행한다. (nv =2 가 끝나면)
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        ch = new int[n + 1];

        //인접 리스트 인덱스 리스트가 노드가 되고, 인덱스 리스트 안에 있는 Integer들이 노드에서 갈 수 있는 접점들이다.
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        ch[1] = 1;
        DFS(1);
        System.out.println(answer);
    }
}

3. 그래프 최단거리(BFS)

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

풀이

public class 그래프최단거리 {
    static int n, m;
    //인접 리스트 방식을 사용한다.
    static ArrayList<ArrayList<Integer>> graph;
	//각 인덱스 값(접점)이 1과 떨어진 최소 거리를 값으로 가진다.
    static int[] answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph=new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        ch = new int[n + 1];
        ch[1] = 0;
        answer = new int[n + 1];
        BFS(1);
        for (int i = 2; i < answer.length; i++) {
            System.out.print(i+" : "+answer[i]);
            System.out.println();
        }
    }

    public static void BFS(int n) {
        Queue<Integer> q = new LinkedList<>();
        int L = 1;
        q.add(n);
        while (!q.isEmpty()) {
            //BFS 방식으로 L에 맞는 q에 갯수만큼 꺼내서
            //해당 접점이 0이면 해당 L에 맞는 값을 answer에 입력하고
            //q에 추가해준다.
            int cnt = q.size();
            for (int i = 0; i < cnt; i++) {
                int current = q.poll();
                for (Integer v : graph.get(current)) {
                    if (answer[v] == 0) {
                        answer[v] = L;
                        q.add(v);
                    }
                }
            }
            L++;
        }
    }
}