(24.09.02) 코딩테스트 알고리즘 정리(전체탐색 : BFS/DFS)

코딩테스트에서 많이 사용되는 알고리즘 중 전체탐색을 하는 BFS DFS 전체탐색 알고리즘을 찾아보고 직접 코드를 짜보면서 학습했다.

 

아래의 모든 내용은 스스로 정리를 한것이고,

이해하기 어려웠기 때문에 코드를 직접 주석과 함께 쓰면서 공부를 하면서 정리하는데 시간이 조금 걸렸지만,

 

전체를 탐색하고 특정 조건이 주어졌을 때, 그 조건을 만족시켜 해당하는 경로(Node)를 탐색시키는 것을 목적으로 둔다는 점에서

BFS는 이웃경로 탐색으로 최단거리, 최단 경로 문제

DFS는 조건이 걸린 모든 경로 구하기문제 = 미로 문제 를 스스로 내서

스스로 알고리즘을 짜면서 학습을 진행을 했다.

 

---

BFS (Breadth-First Search, 너비 우선 탐색)

• 그래프의 모든 노드를 레벨 단위로 탐색하는 알고리즘
  • 따라서 재귀적으로 동작하지 않음, 같은 깊이의 모든 노드를 탐색하는 형태
  • 탐색할 노드에 대해서 방문 여부를 반드시 검사
• 큰 메모리 사용
  • 큐를 사용하므로 메모리 사용이 클 수 있다는 단점

사용 경우

• 최단 경로 찾기, 노드간 경로가 이어져 있는지 확인
  • BFS는 시작 노드에서 다른 노드까지의 최단 경로를 찾는 데 유용
  • 단, 모든 간선(엣지)의 가중치가 동일할 때 = 없을 때
    • 가중치
      • 간선(엣지) 에 할당된 값, 거리 등
      • 가중치가 동일한 경우는 모든 데이터가 같은 거리를 가지고 있는 것 = 단순연결

BFS Algorithm Flow

1. 큐를 사용하여 탐색할 노드를 저장(enqueue)
   • 단, 초기 노드는 집어 넣고 시작해야 반복을 진행시킬 수 있음
2. 시작 노드를 큐에 넣고 방문 표시
3. 큐가 비어있을 때까지 아래를 반복
   1. 큐에서 노드를 꺼내기
   2. 꺼낸 노드, 해당 노드의 모든 인접 노드 탐색
   3. 꺼낸 노드의 인접노드 중 방문기록이 없다면, 탐색한 노드를 큐에 넣고, 이웃노드는 방문 표시

최단거리, 최단경로 계산 문제

임의의 Node와 Edge

package Algorithm;

import java.util.*;

public class BFS {

  public static Map<Integer, List<Integer>> graph = new HashMap<>();

  public static void main(String[] args) {
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
    addEdge(3, 6);
    addEdge(3, 7);

    int start = 4;
    int end = 7;

    Result result = bfs(start, end);

    if (result.minPath == -1) {
      System.out.println("최단 경로를 찾을 수 없습니다.");
    } else {
      System.out.println(start + "부터 " + end + "까지의 최단거리 : " + result.minPath);
      System.out.println(start + "부터 " + end + "까지의 경로 : " + result.nodeDistance);
    }
  }

  // graph 자체에 노드에 관한 간선을 추가하는 메서드
  private static void addEdge(int u, int v) {
    graph.putIfAbsent(u, new ArrayList<>());
    graph.putIfAbsent(v, new ArrayList<>());

    graph.get(u).add(v);
    graph.get(v).add(u);
  }

  private static Result bfs(int start, int end) {

    // start와 end가 똑같을 때 경우
    if (start == end) {
      return new Result(0, null);
    }

    // 방문한 노드 저장 Set (같은 노드를 또 방문할 경우엔 중복시키지 않기 위해서)
    Set<Integer> visited = new HashSet<>();
    // BFS 용 Queue
    Queue<Integer> queue = new LinkedList<>();

    // 최소 거리
    Map<Integer, Integer> distance = new HashMap<>();
    // 최소 경로
    Map<Integer, Integer> parentNode = new HashMap<>();

    // start 세팅
    visited.add(start);
    queue.add(start);
    distance.put(start, 0);
    parentNode.put(start, null);

    while (!queue.isEmpty()) {
      // 노드 꺼내기
      int node = queue.poll();

      // 꺼낸 노드까지의 거리
      int nodeDistance = distance.getOrDefault(node, 0);

      // 이웃 노드 탐색
      for (int neighbor : graph.get(node)) {
        // 방문이력이 없을 경우에만 탐색
        if (!visited.contains(neighbor)) {
          visited.add(neighbor);
          queue.add(neighbor);

          // 노드별 거리 업데이트
          distance.put(neighbor, nodeDistance + 1);
          // 부모 노드 업데이트
          parentNode.put(neighbor, node);

          // 이웃에 end 이 있으면 바로 종료
          if (neighbor == end) {
            // 경로 계산
            List<Integer> minPath = new ArrayList<>();
            Integer currentParent = end; // 경로 복기 시작점
            while (currentParent != null) {
              minPath.add(currentParent);
              currentParent = parentNode.get(currentParent);
            }
            Collections.reverse(minPath);

            return new Result(distance.get(end), minPath);
          }
        }
      }
    }

    // end 에 안걸릴경우
    return new Result(-1, null);
  }

  public static class Result {
    int minPath;
    List<Integer> nodeDistance;

    Result(int minPath, List<Integer> nodeDistance) {
      this.minPath = minPath;
      this.nodeDistance = nodeDistance;
    }
  }
}

---

 

DFS (Depth-First Search, 깊이 우선 탐색)

• 그래프에서 한 노드를 방문을 하되, 그 방문한 노드의 자식 노드의 끝까지 탐색한 뒤, 다음 노드로 넘어가는 전체 탐색 알고리즘
• Stack을 사용하여 구현

사용 경우

• 찾아가는 경로 중 특정 경로의 조건이 있을 때
  • 경로에 같은 숫자가 있으면 안된다 등
  • BFS는 이웃을 찾는 확장 개념이기 때문에 경로로 찾아 들어가는 DFS와 다름
• 미로찾기, 퍼즐게임
  • 가능한 모든 경로를 탐색후에 최단이 아닌 최적의 해결책을 찾을 때까지 탐색하는 것이므로

DFS Algorithm Flow

1. 시작 노드 설정
   • 탐색을 시작할 노드를 선택
     • 노드를 방문했음을 기록이지만, start를 미리 넣어버리면 start 부분 자식은 전부 탐색을 안하기 때문에 세팅X
2. 스택 초기화
   • 초기에는 시작 노드를 스택
3. 스택이 비어있지 않을 때까지 아래의 작업을 반복
   1. 스택에서 노드를 꺼내기
      • 스택에서 노드를 꺼내 현재 노드를 선택 (가장 최신 노드)
   2. 현재 노드의 모든 인접 노드를 탐색
      • 현재 노드와 연결된 모든 이웃 노드를 확인
   3. 이웃 노드를 탐색
      • 이웃 노드 중 아직 방문하지 않은 노드를 찾습니다.
      • 방문하지 않은 이웃 노드를 스택에 넣고, 방문 표시를 합니다.

기본 전체

package Algorithm;

import java.util.*;

public class DFS {

  public static Map<Integer, List<Integer>> graph = new HashMap<>();

  public static void main(String[] args) {
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
    addEdge(3, 6);
    addEdge(3, 7);

    int start = 2;
    System.out.println("DFS 방문 탐색 : " + dfs(start));
  }

  private static void addEdge(int u, int v) {
    graph.putIfAbsent(u, new ArrayList<>());
    graph.putIfAbsent(v, new ArrayList<>());
    graph.get(u).add(v);
    graph.get(v).add(u);
  }

  public static Set<Integer> dfs(int start) {

    // DFS 관련 설정
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();

    // start 초기화 세팅
    stack.push(start);

    while (!stack.isEmpty()) {
      int node = stack.pop();

      // 시작점 부터 방문 시작
      if (!visited.contains(node)) {
        visited.add(node);

        for (int neighbor : graph.get(node)) {
          if (!visited.contains(neighbor)) {
            stack.push(neighbor);
          }
        }
      }

    }
    return visited;
  }
}

재귀적인(Recursive) 접근

• 자기 자신을 계속적으로 호출하는 방식으로 알고리즘을 구성
  • 구성이 훨씬 간단
  • Stack을 사용하지 않는 방법
• BFS일 경우, 주변 Node를 탐색하고 방문했는지의 여부를 검증하는 것이므로 계속 반복해서 Stack을 사용하지 않으므로 재귀적인 접근은 불가
• 기존의 것을 다시 사용하는 것에 있어 스택 메모리가 추가적, 오버헤드의 발생 가능성이 있으나 매우 미미

package Algorithm;

import java.util.*;

public class DFS {

    public static Map<Integer, List<Integer>> graph = new HashMap<>();

    public static void main(String[] args) {
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);
        addEdge(3, 7);

        int start = 2;
        System.out.println("DFS 방문 탐색 : " + dfs(start));
    }

    private static void addEdge(int u, int v) {
        graph.putIfAbsent(u, new ArrayList<>());
        graph.putIfAbsent(v, new ArrayList<>());
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    public static Set<Integer> dfs(int node) {
        Set<Integer> visited = new HashSet<>();
        dfsCheck(node, visited);
        return visited;
    }

    private static void dfsCheck(int node, Set<Integer> visited) {
        visited.add(node);

        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsCheck(neighbor, visited);
            }
        }
    }
}

 

미로찾기 문제

• DFS 알고리즘 중 재귀적 방법을 사용한 미로찾기 알고리즘
  • 스스로 문제를 내고 푸는 방식으로 진행
• 최단 거리가 아닌 모든 가능성을 전체탐색을 통해 알아내는 문제

package Algorithm;

import java.util.*;

public class DFS_Maze_Recursive {

  private static final int[][] MAZE = {
      {0, 1, 0, 0, 0, 0, 1},
      {0, 1, 0, 1, 1, 1, 1},
      {0, 0, 0, 0, 0, 0, 0},
      {0, 1, 0, 1, 0, 1, 0},
      {0, 1, 1, 0, 0, 1, 0},
      {0, 0, 1, 0, 1, 1, 0},
      {1, 0, 1, 0, 0, 0, 0}
  };

  // 방향 관련
  private static final int[] DX = {-1, 1, 0, 0};
  private static final int[] DY = {0, 0, -1, 1};

  public static void main(String[] args) {
    // 입구
    int startX = 0;
    int startY = 0;

    // 출구
    int endX = 6;
    int endY = 6;

    List<List<int[]>> allPath = dfs(startX, startY, endX, endY);

    System.out.println("다음은 모든 경로:");
    for (List<int[]> path : allPath) {
      StringBuilder stringBuilder = new StringBuilder();
      for (int[] position : path) {
        stringBuilder.append("(" + position[0] + "," + position[1] + ") ");
      }
      System.out.println(stringBuilder);
    }
    //(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4) (4,3) (5,3) (6,3) (6,4) (6,5) (6,6)
    //(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (3,6) (4,6) (5,6) (6,6)
  }

  private static List<List<int[]>> dfs(int startX, int startY, int endX, int endY) {
    boolean[][] visited = new boolean[MAZE.length][MAZE[0].length];
    List<int[]> path = new ArrayList<>();
    List<List<int[]>> allPath = new ArrayList<>();

    dfsCheck(startX, startY, endX, endY, visited, path, allPath);

    return allPath;
  }

  private static void dfsCheck(int startX, int startY, int endX, int endY, boolean[][] visited,
      List<int[]> path, List<List<int[]>> allPath) {
    // 경로 유효성 검사
    // 좌표가 미로 범위에 있는지 검증
    // 해당 좌표가 통로인지 검증
    // 이미 방문한 좌표인지 검증
    if (startX < 0 ||
        startX >= MAZE.length ||
        startY < 0 ||
        startY >= MAZE[0].length ||
        MAZE[startX][startY] == 1 ||
        visited[startX][startY]) {
      // 어느 하나라도 해당하면 그냥 넘기기
      return;
    }

    // 출구에 도달한 경우
    if (startX == endX && startY == endY) {
      path.add(new int[]{startX, startY});
      allPath.add(new ArrayList<>(path));
      // 백트래킹
      path.remove(path.size() - 1);
      return;
    }

    // 정상 진행
    // 현재 위치 방문 표시
    visited[startX][startY] = true; // contains로 다 훑는 것이 아니라 그냥 해당 부분만 boolean인지 확인
    path.add(new int[]{startX, startY});

    // 상하좌우로 재귀적으로 탐색
    for (int i = 0; i < 4; i++) {
      int newX = startX + DX[i];
      int newY = startY + DY[i];

      dfsCheck(newX, newY, endX, endY, visited, path, allPath);
    }

    // 상하좌우(검증 에서 return이 있을경우) 백트래킹
    visited[startX][startY] = false;
    path.remove(path.size() - 1);
  }
}

 

---

전체탐색 알고리즘을 알지 못한 경우 모든 경우의 수를 일일히 하나하나 확인을 해야하는 로직을 모두 구축을 해야하기 때문에, Node와 Edge 역할을 코딩테스트 문제에서 파악해서 로직으로 구축을 하고 진행을 할 경우

BFS DFS 알고리즘으로 전체탐색을 빠르고 쉽게 답을 도출할 수 있을 것이라고 생각