인프런 JAVA 알고리즘 정리(DFS, BFS 기초 7~14번)

7. 이진트리 레벨탐색 (BFS)

- 최단거리 (목적지 까지 몇번만에 갈 수 있는지)

- for문이 끝나면 레벨 증가 

- Queue<Integer> queue = new LinkedList<>();

 

 

8. 송아지 찾기 (BFS) - 최단거리

- 앞으로 1, 뒤로 1, 앞으로 5칸 갈 수 있다면 송아지 위치까지의 최단거리는?

- 나의 위치 4 송아지 위치 5 -> 앞으로 한칸으로 1번 최단거리

- 나의 위치 5 송아지 위치 11 -> 앞으로 한칸 + 앞으로 5칸 2번 최단거리 

 

Queue

public static int BFS(int me, int song){
    int count = 0;
    ch = new int[10004];
    ch[me] = me;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(me);
    while(!queue.isEmpty()){
        int length = queue.size();
        for(int i=0; i<length; i++){
            int l = queue.poll(); // queue에서 뽑는다.
            if(l==song) return count;

            if(ch[l-1]==0 && l-1>0) queue.add(l-1); // 1부터 10000사이 이기에
            if(ch[l+1]==0) queue.add(l+1);
            if(ch[l+5]==0) queue.add(l+5);
            ch[l-1] = l-1;
            ch[l+1] = l+1;
            ch[l+5] = l+5;
        }
        count++;
    }
    return 0;
}

 

 

9. Tree 말단노드까지의 가장 짧은 경로(DFS)

- 이와 같은 최단거리 문제는 BFS로 푸는게 정석 

- 1에서 말단노드인 3이 가장 짧고 길이는 1이다.

결국 마지막 노드에서 리턴이 일어남으로 4에서 2리턴 5에서 2리턴 2번 노드에서는 2로 리턴이 된다. 말단 노드인 3에서는 1리턴 그리고 최종적으로 루트1에서는 2와 1중 작은값인 1을 선정

public static int DFS(int L, Node root){
    if(root.lt == null && root.rt==null) return L; //말단 노드
    else return Math.min(DFS(L+1, root.lt), DFS(L+1,  root.rt));
    // 재귀로 이루어져있기에 루트 들이 바뀌면서 작은값이 계속 타고 타고 올라오게 된다.
}

 

 

 

10. Tree 말단노드까지의 가장 짧은 경로(BFS)

-> Queue에 노드를 집어 넣을 때 노드의 좌우 자식이 없다면 현제 레벨값 리턴

 

 

11. 그래프와 인접행렬

그래프<Vertex, Edge> ( 무방향 그래프, 방향 그래프, 가중치 방향그래프 )

- 2차원 배열로 간선 정보를 처리

 

 

12. 경로 탐색(인접 행렬)

public static int DFS(int[][] arr, int n){
    if(n==arr.length-1){
        return cnt++;
    }else{
        ch[1]=1;
        for(int i=1; i<arr.length; i++){
            if(arr[n][i]==1 && ch[i]==0) {
                ch[i]=1; // 방문했던 노드 재방문 금지
                DFS(arr, i);
                ch[i]=0; // 방문이 끝나면 다시 방문 가능
            }
        }
    }
    return cnt;
}

 

 

13. 경로 탐색(인접 리스트)

- 정점이 1000개, 10000개이면 인접행렬은 비효율적 -> for문을 정점마다 1000번 10000번을 돌아야한다. -> 인접리스트

Array리스트를 객체로 가지는 ArrayList를 선언해야 된다.

각각의 Array리스트를 생성해서 ArrayList 객체에 넣는다.

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int edge = scan.nextInt();
    int line = scan.nextInt();
    ArrayList<ArrayList> arrayList = new ArrayList();
    for(int i=0; i<edge+1; i++){
        ArrayList<Integer> arr = new ArrayList<>();
        arrayList.add(arr);
    }
    for (int i = 0; i < line; i++) {
        int a = scan.nextInt();
        int b = scan.nextInt();
        arrayList.get(a).add(b);
    }
    ch = new int[6];
    ch[1] = 1;
    System.out.println(DFS(arrayList, 1));
}

public static int DFS(ArrayList<ArrayList> arr, int n) {
    if (n == 5) {
        return cnt++;
    } else {
        ArrayList<Integer> arrayList = arr.get(n);
        for (int x : arrayList) {
            if (ch[x] == 0) {
                ch[x] = 1; // 방문했던 노드 재방문 금지
                DFS(arr, x);
                ch[x] = 0; // 방문이 끝나면 다시 방문 가능
            }
        }

    }
    return cnt;
}

 

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

static 배열에 작은 값을 업데이트하며 각 노드의 최단거리를 저장  ( 전의 정점 값에서 + 1 )