코딩테스트 탐색문제 (DFS,BFS,DP)

그래프이론으로 정의되는 문제

• 그래프 탐색문제 : 그래프를 노드간 관계(함수 혹은 adj list 관계 등)로 표현하고 각 노드를 탐색한 후 특정한 동작/함수를 실행함.
  • 노드를 특정한 경우의 수로 생각할 수 있으며 코드로는 객체의 특정한 상태(state) 로 표현함, 각 노드는 객체의 attribute 값이 다른 상태.
  • 그래프 탐색 문제 풀이의 관건은 노드/경우의 수를 어떻게 객체와 개체의 attribute로 표현할 것인지. 그리고 노드간 의 관계인 엣지는 어떤 Method 관계(객체의 attribute를 바꾸는 함수)로 표현할 것인지. 그리고 더 나아가 시간복잡도 최적화를 위해서 엣지 커트를 어떻게 구현할 것인지에 대한 문제이다.

DFS와 For/if문 차이

• 경우의 수 관점에서는 컴퓨터의 모든 동작은 tree로 나타낼 수 있다. 분기를 활용하는 if/for문 그리고 재귀함수(DFS,BFS)는 결국 동일하게 tree와 같이 분기를 형성한다. for문은 i를 활용해서 분기마다 다른 값을 적용할 수 있으며 재귀함수는 Parameter을 통해서 다른 값을 적용할 수 있다. 
• for문/if문과 재귀함수의 차이는,
  • for/if문은 분기의 중첩개수가 for/if구문의 개수에 따라 유한하지만 DFS의 경우 parameter를 통해서 개수를 설정할 수 있다는 것이다.
  • 주로, 구조는 DFS 함수 내에서 for문이 존재하고 for문의 중첩개수 혹은 중첩구조를 DFS 함수 parameter로 custom함. 

DFS와 BFS 설계고려요소

• 1. main logic : node에 도달하엿을때 어떤 기능을 실행할 것인가 (for문, stack의 push pop, chk의 =1,0)
• 2. parameter : 어떤 parameter을 갖고서 노드 간의 관계 (edge)는 어떻게 정의할 것인지? 
• 3. edge cut : 언제까지 재귀함수를 실행시킬 것이며 edge cut가 필요하다면 어떻게 구현할 것인지?
  • DFS와 BFS 모두 경로탐색을 목적으로하지만 DFS은 depth를 우선으로 탐색하기 때문에, depth가 너무 깊은 경로의 경우 수행시간이 무한정 오래 걸릴 수 있다. 반면 BFS는 level별 탐색이기때문에 최단경로 탐색에 적합하다.

DFS

정의 개념

 

설계방식

• 1. 현재 Node에서 다음 Node와의 관계를 DFS Parameter로 재귀함수로 정립 
• 2. 분기할 횟수만큼 For문 순회하여 DFS 호출
• 3. Cutedge를 위한 CHK와 Level 등 적용

적용시점

• 탐색가능한 경로 중 더이상 탐색이 불가할 때까지 순차적으로 탐색하는 방법.

 

DFS 유형분류

1. 실행함수의 위치를 통해 출력값조절한 DFS

// n ... 5, 4, 3, 2, 1
    public void Dfs1(int n){
        if(n == 0) // cutedge
            return;
        else{
            System.out.print(n + " "); // main logic
            Dfs1(n-1); // exploring
        }
    }

    // 1, 2, 3, 4, 5...
    public void Dfs2(int n){
        if(n == 0) // cutedge
            return;
        else{
            Dfs2(n-1); // exploring
            System.out.print(n + " "); // main logic
        }
    }

    // 1, 2, 4, 5, 3, 6 ,7  전위순회 tree exploration, 중위 및 후위는 순서만 바꾸면됨
    public void Dfs3(int v){
        if(v > 7)  // cutedge
            return;
        else{
            System.out.print(v + " "); // main logic
            Dfs3(v*2);  // exploring
            Dfs3(v*2+1); // exploring
        } 
    }

 

 

2. Level Parameter로 중첩 횟수를 정의한 DFS (중복조합)

• Level와 종료시점을 parameter로 저장하여 중첩회수 정의
• Stack을 통해서 depth에 따른 결과물들을 저장

// 중복순열- 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복과 상관없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는것
Stack<Integer> pm = new Stack<>();

public void Dfs1(int Level, int n, int r) {
    if (Level == r) { // cut edge
        for (int x : pm) {
            System.out.print(x + " ");
        }
        System.out.println();
    } else { // main logic
        for (int i = 1; i <= n; i++) {
            pm.push(i);
            Dfs(Level + 1, n, r); // exploration
            pm.pop();
        }
    }
}

 

 

3. CHK로 중복을 제거하는 DFS (순열)

• stack 구조로 다른 node로 이동하기전에 check in 탐색완료후 check out

// 순열 : 서로 다른 n개의 원소를 가지는 어떤 집합에서 '중복 없이' '순서에 상관있게' r개의 원소를 선택하거나 혹은 나열하는 것
Stack<Integer> stack = new Stack<>();
public void Dfs2(int L, int n, int r, int[] ch) {
    if (L == r) {
        for (int x : pm) {
            System.out.print(x + " ");
        }
        System.out.println();
    } else {
        for (int i = 1; i <= n; i++) {
            if (ch[i] == 0) {
                ch[i] = 1;
                pm.push(i);
                Dfs2(L + 1, n, r, ch);
                ch[i] = 0;
                pm.pop();
            }
        }
    }
}

 

4. Str과 End을 조정해서 분기를 만드는 DFS (조합)

Stack<Integer> combi = new Stack<>();

public void DFS(int L, int s, int n, int r) {
    if (L == r) {
        for (int x : combi) System.out.print(x + " ");
        System.out.println();
    } else {
        for (int i = s; i <= n; i++) {
            combi.push(i);
            DFS(L + 1, i + 1, n, r);
            combi.pop();
        }
    }
}

 

BFS

레벨별로 그래프를 탐색

 

Que로 정의된 BFS

DFS가 Stack을 활용하여 LIFO순서로 전개해 나간다면, BFS는 que를 활용하여 FIFO순서로 전개해 나간다.

 

설계방식

• 1. Que 안의 개수를 저장하고 횟수만큼 For문 순회하여 poll
• 2. 뽑혀진 Node에서 다음 Node와의 관계를 정립 
• 3. 분기할 횟수만큼 For문 순회하여 새로운 Node를 offer

적용시점

• 횟수라는 단어가나오면 BFS로 풀이
• 횟수로 도달할 수 있는 경로이면 BFS로 풀이
  • 단, 이미 도달했던 경로는 chk로 반복하지 않도록 함.

 

 

 

•  중첩 횟수를 정의한 BFS
  • 1. CutEdge는  nextnode가 queue에 들어가기 전에 cut

public void BFS() {
    Queue<Integer> Q = new LinkedList<>();
    // 루트노드 입력 및 레벨정의
    Q.offer(1);
    int L = 0;

    while (!Q.isEmpty()) {
        // 각 레벨별 큐에서 poll 할 횟수 정의 후, poll 진행
        int n = Q.size();
        for (int i = 0; i < n; i++) {
            int v = Q.poll();
            // 각 노드에서 실행할 로직 정의
            System.out.print(v + " ");
            // 탐색할 다음 노트 입력 및 edge cut
            for (int nv : new int[]{v * 2, v * 2 + 1}) {
                if (nv > 7) continue;
                Q.offer(nv);
            }
        }
        // 레벨 증가
        L++;
    }
}

 

•  CHK로 중복을 제거하는 BFS
  • 중복 check list는 nextnode가 queue에 들어가는 순간 1로 표기

int BFS(int root, int target) {
    Queue<Integer> queue = new LinkedList<>();
    // que 생성하여 root 삽입 + 방문한 노드는 chklist에 chk
    int[] chk = new int[10000 + 1];
    int level = 0;
    queue.add(root);
    chk[root] = 1;
    
    while (!queue.isEmpty()) {
        //레벨 증가후,queue 안의 node 개수만큼 poll할 횟수 결정
        int loopNumber = queue.size();
        for (int i = 0; i < loopNumber; i++) {
            int node = queue.poll();
            // 노드에 도착한 후의 로직실행
            System.out.println(node);
            if (node == target) {
                //값 배치후 loop에서 탈출
                return result;
            }
            // 다음 노드를 전개하여 큐에 저장
            for (int nextnode :
                    new int[]{node + 1, node - 1, node + 5}) {
                //큐에 들어가기 전 cutedge실행 
                if (nextnode > 0 && chk[nextnode] == 0) {
                    queue.add(nextnode);
                    //중복제외
                    chk[nextnode] = 1;
                }
            }
        }
        level++;
    }
    return -1;
}

 

• 경로탐색하는 BFS
  
  • 중복 check list는 nextnode가 queue에 들어가는 순간 1로 표기

public class GameDistance {

    static int[] movx = {1, 0, -1, 0};
    static int[] movy = {0, 1, 0, -1};
    
    public int solution(int[][] maps) {
        int[][] chk = new int[maps.length][maps[0].length];
        return BFS(0, chk, maps);
    }

    public int BFS(int level, int[][] chk, int[][] maps) {
        Queue<int[]> que = new LinkedList<>();
        chk[0][0] = 1;
        que.offer(new int[]{0, 0});

        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] cur = que.poll();
                if (cur[0] == maps.length - 1 && cur[1] == maps[0].length - 1) {
                    return level + 1;
                }

                for (int j = 0; j < 4; j++) {
                    int mova = cur[0] + movx[j];
                    int movb = cur[1] + movy[j];
                    if (0 <= mova && mova <= maps.length - 1 && 0 <= movb && movb <= maps[0].length - 1 && chk[mova][movb] == 0 && maps[mova][movb] == 1) {
                        chk[mova][movb] = 1;
                        que.offer(new int[]{mova, movb});
                    }
                }

            }
            level++;
        }
        return -1;

    }
}

BloodFill

 

 

 2차원배열 : int[row][column]

{

{array1 .............},  row0

{array2 .............}, row1

{array3 .............}, row2

{array4 .............}, row3

{array5.............}, row4

{array6.............}, row5

{array7.............}, row6

}

 

 

 

 

 

DFS와 BloodFill

• 4방향의 움직임을 movx와 movy로 미리 정의하고 For문 하나로 4방향을 분기 
• cutedge로 1. 좌표가 보드 안일것 2. chk가 안된 곳일 것 

public static class solution {
    static int [] movx = {0,0,1,-1};
    static int [] movy = {1,-1,0,0};
    static int cnt = 0;
    public static int solution(int[][] board) {
        cnt = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == 1) {
                    cnt++;
                    DFS(new int[] {i, j}, board);
                }
            }
        }
        return cnt;
    }

    public static void DFS(int[] cur, int[][] board)
    {
        int[] next = new int[2];
        for (int i = 0; i < 4; i++) {
            next[0] = cur[0]+movx[i];
            next[1] = cur[1]+movy[i];
            if (0<=next[0]&&next[0]<board.length&&0<=next[1]&&next[1]<board.length&&board[next[0]][next[1]] == 1) {
                board[next[0]][next[1]] = 0;
                DFS(next, board);
            }
        }
    }
}

 

BFS와 BloodFill

 

 

Divide&Conquer와 BloodFill

 

 

인접리스트 표현법

 

edge들을 탐색해서 시작 Vertex를 index에 위치한 List에 갈수 있는 Neighbor 객체를 추가하는방식. 코테에서 인접리스트 사용이 선호된다.

 

 

 

Dynamic Programming

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 간단한 하위 문제로 나누어 푸는 최적화 기법. 큰문제를 작은 문제로 나누어서 큰문제와 작은 문제같의 점화식 관계를 찾아내는게 관건이다. 그리고 기초값들을 배열에 저장하여 점화식의 값을 순서대로 쌓아나간다.

• 접근방법
  • 경우의수를 어떤 기준으로 MECE하게 나눌 수 있을지 고민후 나눠본다
  • 경우의 수 간의 점화식을 찾는다.
• 다이나믹 프로그래밍 판별법
  • 우선, 그리디, 구현, 완전탐색으로 문제를 풀어보고 풀이방법이 마땅하지 않다면 다이나믹 프로그래밍을 적용해본다. 재귀함수로 비효율적인 완전탐색을 구현한 후에 작은문제의 답이 큰문제의 답으로 적용가능한지 확인한다.
• 유형정리
  
  • 계단오르기 (1단, 2단, 3단) ; 값이 증가하는 방식을 경우의 수를 나누어 부분으로 쪼개어 점화식을 구함
    • 바텀업방식 : 시작점으로부터 계단을 오르는 경우의 수를 정해서, 계단을 오르는 경우의 수는 최초에 1단으로 오르는 방법, 2단으로 오르는 방법, 3단으로 오르는 방법으로 크게 나뉠 수 있다. 따라서, 4단 계단을 오르는 방법은 a1+a2+a3로 표현가능함.
    • 업다운방식 : 도착점으로부터 계단을 올라온 경우의 수를 정해서, 계단을 마지막으로 오른 경우의 수를 
  • LIS 최대 부분 증가수열 ; 주어진 수열에서 원래 순서를 유지하면서, 값이 점점 증가하는 부분 수열 중 가장 긴 것을 찾는 문제 
    • dp[i]를 arr[i]를 마지막 원소로 하는 LIS의 길이로 정의한다.  dp[i]를 구할 때, 자신보다 앞에 있는 원소 중 arr[j] < arr[i]인 원소들만 고려하여 최댓값을 선택하고 +1을 한다.
  • 냅색문제 ; 제한된 용량을 가진 배낭에 여러 개의 물건을 넣을 때, 최대,최소의 가치의 조합을 찾는 문제
    • 배낭의 최대 용량 크기만큼의 배열(dp)을 정의하고, 배열의 i번째 인덱스를 용량 i 내에서의 최대(또는 최소) 가치로 설정한다. 점화식 관계를 활용하여, 특정 용량 i에서 어떤 아이템(a 용량, value 가치)을 선택하면 i + a 위치로 이동하면서 가치값을 더하여 업데이트한다.
      • 냅색문제를 DFS로 나눈다면 경우의수를 나눌때, 물건의 개수를 기준으로 나누고 최소값을 저장하여 개수와 가치의 합으로 cutedge하는 방법을 사용
      • DP는 특정 값의 최소값을 구하는 방법을 이하 값의 점화식 관계로 구함.

 

점화식과 재귀함수

• 재귀함수 : 함수 내에서 자기자신을 호출하는 함수, 코드 내에 자기자신을 호출하는 점화식 구조를 가지고 있음 (A(n+1) = A(n) + alpha). 
  • PS관점에서는 반복문의 대체재이며, 복잡한 반복문의 코드 유연성과 가독성을 확보할 수 있음. 단, 함수반복의 종료시점에 대해서 정의를 해주어야함.
  • 재귀함수는 스택자료구조를 활용, 코드의 호출 순서대로 call 된 코드가 쌓이며 차례대로 연산되는 구조.
  • 1부터 N까지 출력하는 함수
    • def f(n) : if n >0 / print(n) / f(n-1)
  •  피보나치 재귀함수 구현
    • def fib(n): if n==1 or n==2: / return 1 /else: /return fib(n-1) + fib(n-2)
  •  피보나치 반복문 구현
    • def fib(n): a,b = 1,1 / if n==1 or n==2: / return 1 / for i in range(1,n):/ a,b = b, a+b / return a
• 유형정리