[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS -2

경로 탐색

DFS 방향 그래프

import java.util.*;

public class Main {

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

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

    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        grape = new int[n+1][n+1];
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            grape[a][b] = 1;
        }

        ch[1]=1;
        t.DFS(1);
        System.out.println(answer);
    }
}

정리
1. 일단 정점 n과 방향 이동 m개의 선이 있음을 받음
2. 각 정점의 이동경로가 있는지 입력받기 위해 n*n으로 이루어진 2차원배열을 만듬
3. m번의 반복을 돌아서 이동이 있는 데이터를 (a경로에서 b의 경로) 입력 받고, 확인되었다면 그래프배열 a,b의 값을 1로 바꿈
4. 재귀함수를 돌았는지 체크하기 위해 사이즈 n의 1차원배열도 만들어줌
5. 재귀함수에 찾고자하는 끝점의 데이터가 들어왔다면 answer을 증가
6. 끝점이 아니라면 반복을 돌면서 1부터 n까지의 방향을 돌되
7. 이미 방문한 정점은 배제(ch가 1이 아닐경우), 그래프에 존재하지 않는 이동경로라면 배제(그래프배열 a,b의 값이 1이 아닐경우)
인접리스트

import java.util.*;

public class Main {

    static int n, m;
    static int answer = 0;
    static ArrayList<ArrayList<Integer>> grape;
    static int[] ch;

    public void DFS(int v){
        if(v==n) {
            answer++;
        }
        else {
            for (Integer integer : grape.get(v)) {
                if(ch[integer]==0) {
                    ch[integer]=1;
                    DFS(integer);
                    ch[integer]=0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        grape = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++){
            grape.add(new ArrayList<Integer>());
        }
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            grape.get(a).add(b);
        }

        ch[1]=1;
        t.DFS(1);
        System.out.println(answer);
    }
}

정리
1. 행렬로 구현하는것은 정점의 수가 많아진다면 상당히 비효율적임
2. 리스트<리스트()>() 형식으로 생성하고 이때 각 정점에 해당하는 그래프에 해당 정점이 이동하는 정점을 추가하는 방식으로 구현함
3. 일단 정점수를 입력받았다면 반복문을 통해 정점+1만큼의 각 리스트를 1차 리스트에 추가해줌 (0은 사용하지 않기에 +1 해야함)
4. 이동데이터를 확인하여 각 정점 리스트에 이동정점을 추가해줌
5. DFS로 접근하는 방식은 행렬과 동일
6. 다만 행렬에서는 for문보다 foreach문을 사용하는 것이 효율적

그래프 최단거리

BFS 풀이

import java.util.*;

public class Main {

    static int n;
    static int[] chk;
    static List<List<Integer>> list = new ArrayList<>();
    public void BFS(List<List<Integer>> list){
        Queue<Integer> q = new LinkedList<>();
        for(int i=2; i<=n; i++){
            int L = 0;
            q.add(1);
            while(!q.isEmpty()){
                int size = q.size();
                for (int j=0; j<size; j++){
                    int num = q.poll();
                    chk[num]=1;
                    if(num==i) {
                        System.out.println(num+" : "+L);
                        q.clear();
                    } else {
                        for (Integer integer : list.get(num)) {
                            if(chk[integer]==0) q.offer(integer);
                        }
                    }
                    if(q.isEmpty()) break;
                }
                L++;
            }
            for(int j=1; j<chk.length; j++) {
                chk[j]=0;
            }
        }
    }

    public static void main(String[] args) {

        Main m = new Main();
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int cnt = scan.nextInt();
        for(int i=0; i<=n; i++){
            list.add(new ArrayList<>());
        }
        for(int i=0; i<cnt; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            list.get(a).add(b);
        }
        chk = new int[n+1];

        m.BFS(list);
    }
}

정리
1. 일단 최단거리 문제라 BFS 방식을 사용하여 풀이
2. 그래프는 미리 이중그래프 형식으로 만들어 저장해 매개변수로 전달받는 형식으로 구현함
3. 정점별로 답을 찾아야 하기에 정점의 수만큼 (단 시작점인 1은 제되) 반복을 돌아 각 i와 일치하는 값을 찾도록 하였고
4. 매번 1을 시작점으로 큐에 추가하여 그래프를 트리형식으로 읽어내림
5. 이때 트리의 정점에 방문할때마다 체크배열을 1로 바꾸어주었고
6. 해당 정점이 i와 일치할때 콘솔에 현재 레벨을 출력
7. 그리고 해당 정점의 최단거리는 찾은것이기에 더는 반복할필요가 없으므로 큐를 지워줌
8. 그리고 큐가 비어있을때는 break 되게 함
9. 일치하지 않을경우에는 해당 정점에서 하위로 뻗어나가는 자식노드들을 큐에 추가
10. 해당 레벨에 데이터가 없다면 L을 증가해주고 큐를 계속해서 반복되게 하였음
개선 풀이 (반드시 복습 필요)

import java.util.*;

public class Main {

    static int n;
    static int[] chk, dis;
    static List<List<Integer>> list = new ArrayList<>();
    public void BFS(int v){
        Queue<Integer> q = new LinkedList<>();
        chk[v] = 1;
        dis[v] = 0;
        q.offer(v);
        while(!q.isEmpty()){
            int cur = q.poll();
            for (Integer nv : list.get(cur)) {
                if(chk[nv]==0){
                    chk[nv]=1;
                    q.offer(nv);
                    dis[nv]=dis[cur]+1;
                }
            }
        }
    }

    public static void main(String[] args) {

        Main m = new Main();
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int cnt = scan.nextInt();
        for(int i=0; i<=n; i++){
            list.add(new ArrayList<>());
        }
        for(int i=0; i<cnt; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            list.get(a).add(b);
        }
        chk = new int[n+1];
        dis = new int[n+1];

        m.BFS(1);
        for(int i=2; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
    }
}

정리
1. 이중 리스트를 만들어 큐로 접근하는 방식까지는 동일
2. 이때 거리를 담아두는 dis배열을 하나 더 만듬
3. 초기에 chk=1로 방문체크하고 당사자는 이동거리가 없으니 dis=0으로 초기 셋팅
4. BFS식으로 접근하는것은 맞지만 레벨을 이용하는 것이 아니라
5. 현재 정점을 꺼내서 저장
6. 현재 정점에서 이동되는 이동 정점들의 반복문을 동작
7. 이동정점이 방문한적 없는 정점이라면 방문값을 1로 바꾸고 큐에 추가
8. 이동값은 이동[이전정점]+1 로 반영함

훨씬 간편하고 간략하고 효율적인 방식이므로 반드시 머릿속에 익혀두어야 함

IM

경로 탐색

그래프 최단거리