[코드스테이츠] 05_16_TIL : 알고리즘/자료구조 _ Tree, Graph Search Algorithm

Today I Lean

알고리즘/자료구조 _ Tree, Graph Search Algorithm

 

 

 

 

 

 

 

배운 것

# Tree Traversal

1. 트리 순회

 : 특정 목적을 위해 트리의 노드를 한 번 씩 방문하는 것

 → 항상 왼쪽에서 오른쪽으로 순회

 

- 전위 순회 (Preorder Traverse)

• 가장 먼저 방문  : 루트
• 왼쪽의 노드를 탐색  → 오른쪽 노드탐색

 → 트리를 복사할 때 주로 사용

if (node != null) {
      list.add(node.getData());
      list = preOrder(node.getLeft(), list);
      list = preOrder(node.getRight(), list);
    }
    return list;

 

 

- 중위 순회 (Inorder Traverse)

• 루트를 가운데 두고 순회
• 제일 왼쪽 끝에 있는 노드부터 순회
• 왼쪽 → 루트 → 오른쪽

 → 오름차순으로 값을 가져올 때 사용

    if (node != null) {
      list = inOrder(node.getLeft(), list);
      list.add(node.getData());
      list = inOrder(node.getRight(), list);
    }
    return list;

 

 

- 후위 순회 (Postorder Traverse)

• 루트를 마지막에 순회
• 제일 왼쪽 끝에 있는 노드부터 순회
• 왼쪽 → 오른쪽 → 루트

 → 트리를 삭제할 때 사용 (자식 노드가 먼저 삭제 되어야 부모노드 삭제 가능)

    if (node != null) {
      list = postOrder(node.getLeft(), list);
      list = postOrder(node.getRight(), list);
      list.add(node.getData());
    }
    return list;

 

 

 

 

2. 이진 트리와 BST 이외에 어떤 트리가 있을까?

 

 

 

 

3. 균형 이진 탐색 트리란?

 

 

 

 

#  Graph Traversal

1. 그래프의 탐색이란?

 : 하나의 정점에서 시작해서, 모든 정점들을 한 번 씩 탐색 하는 것이 목적

 → 그래프의 데이터는 배열처럼 정렬되어있지 않아서 모두 방문하여 데이터를 찾아야 함

 

 

 

2. BFS (Breadth - First Search)

 : Queue를 활용하여 구현

 → 너비 우선 탐색

 → 첫번째 경로가 찾는 값이라도, 모든 경로를 다 살펴봐야 함

 

 

- 특징

• 하나의 정점을 기준으로 인접한 정점을 모두 방문
• 기준점을 방문했던 정점으로 변경, 해당 정점과 인접한 정점을 모두 방문
• 최상위 정점을 기준으로 찾는 값이 나올 때 까지 이어진 정점들을 차례로 방문함

 → 주로 두 정점 사이 최단 경로를 찾을 때 사용

 → visited 배열과 같은 방문여부를 체크하는 자료구조를 사용해야함 (사용하지 않을시 무한루프에 빠질 수 있음)

 

 

- 구현 방법

• 시작노드는 큐에 삽입한 후, 인접한 노드를 차례로 큐에 삽입하면서 탐색을 진행
• Queue를 사용하여 구현
• 시작노드를 큐에 삽입, 큐가 빌 때 까지 반복 실행
• 큐에서 현재 정점 추출 → queue.poll()
• 현재 정점은 이미 이동했다고 방문여부 체크 → visited[start] = true;
• poll()을 활용해 가져온 정점을 기준으로 인접한 정점을 모두 큐에 삽입  → queue.offer()
• 큐가 빌 때 까지 반복 실행

public ArrayList<Integer> shortestPath(int[][] graph, int start, int end) {
  boolean[] visited = new boolean[graph.length];
  return bfs(graph, start, end, visited);
}

public ArrayList<Integer> bfs(int[][] graph, int start, int end, boolean[] visited) {

int[][] graph = {
            {0, 1, 1, 0, 0, 0},
            {1, 0, 0, 1, 1, 0},
            {1, 0, 0, 0, 0, 1},
            {0, 1, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 1},
            {0, 0, 1, 0, 1, 0}
        };
int start = 0;
int end = 5;


  //bfs의 경우 큐를 사용합니다.
  Queue<Integer> queue = new LinkedList<>();
  int[] parent = new int[graph.length];

  queue.offer(start);
  visited[start] = true;
  // 현재 기준점을 확인할 배열
  parent[start] = -1;

  while (!queue.isEmpty()) {
    int node = queue.poll();

    // 도착점까지 도달한다면
    if (node == end) {
      ArrayList<Integer> path = new ArrayList<>();
      while (node != -1) {
        path.add(node);
        node = parent[node];
      }
      // 데이터 뒤집기
      Collections.reverse(path);
      return path;
    }

    for (int i = 0; i < graph.length; i++) {
      if (graph[node][i] == 1 && !visited[i]) {
        queue.add(i);
        visited[i] = true;
        parent[i] = node;
      }
    }
  }
  // 끝까지 길을 찾기 못한 경우, null을 반환.
  return null;
}

 

 

 

 

3. DFS (Depth - First Search)

 : Stack, 재귀를 활용하여 구현

 → 깊이 우선 탐색

 

- 특징

• 하나의 경로를 끝까지 탐색
• 더 탐색할 정점이 없을 때, 다음 경로를 탐색

 → 경로 하나씩 완벽하게 탐색할 때 사용

 → 그래프 내의 순환구조 (Cycle)를 고려하여 방문한 정점을 다시 방문하지 않도록 해야 함

 

 

- 구현방법

• Stack 자료구조나 재귀를 통해 구현 가능 (일반적으로 재귀 사용)
• 방문했던 정점인지 확인, 방문했다면 재귀호출을 종료 (단순 출력이 아닌 방문여부를 저장할 데이터가 필요하다면 해당 데이터에 방문 여부를 저장하고, 저장한 데이터를 반환)
• 방문하지 않았다면, 방문여부 체크  →visitied[index[ = true;
• 해당 정점에 연결된 모든 정점을 재귀호출로 순회 

class Solution {
    public int numIslands(char[][] grid) {
    
    int grid[][] = new int[][]{
      {"1","1","1","0","0"},
      {"1","1","0","0","0"},
      {"1","1","0","0","1"},
      {"0","0","0","1","1"}
    };
				// 입력된 grid가 비어있을 경우, 섬이 존재하지 않으므로 0을 반환합니다.
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numIslands = 0; // 섬의 수를 담을 변수를 선언, 초기화
        int numRows = grid.length; // Row의 최대 길이
        int numCols = grid[0].length; //Col의 최대 길이

				// 대륙을 순회합니다. 이중 loop
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
								// 현재 방문한 정점이 1이라면(섬이라면)
                if (grid[i][j] == '1') {
                    numIslands++; // 섬의 수를 증가시키고
                    dfs(grid, i, j); // DFS를 호출하여 주변의 이어진 섬이 있는지 확인합니다.
                }
            }
        }

        return numIslands;
    }

    private void dfs(char[][] grid, int row, int col) {
				// 섬의 최대 길이 확인
        int numRows = grid.length;
        int numCols = grid[0].length;

				// 이동 후, 섬의 크기를 벗어난 경우(예외 처리)
        if (row < 0 || col < 0 || row >= numRows || col >= numCols || grid[row][col] == '0') {
            return;
        }

				// 현재 방문한 땅을 0 할당(방문 여부 체크)
        grid[row][col] = '0';

				// Down, Up, Right, Left 이동을 재귀 호출을 통해서 처리
        dfs(grid, row + 1, col);
        dfs(grid, row - 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row, col - 1);
    }
}

 

 

 

4. BFS, DFS 비교

- 장단점

	BFS	DFS
장점	두 정점 사이의 최단경로를 찾을 때 유리	하나의 노선을 끝까지 확인, 운이 좋다면 빠르게 경로를 찾을 수 있음
		모든 정점 탐색 가능
		현 경로상의 정점만 기억하면 되기 때문에 메모리 사용이 비교적 적음
		찾는 값이 깊은 곳에 있다면 빠르게 찾을 수 있음
단점	메모리 사용이 큼	도달할 정점이 없다면 무한루프에 빠질 수 있음
	그래프의 크기와 밀도에따라 성능이 달라짐 그래프의 밀도가 높으면 (간선의 개수가 많으면=정점이 많으면) 성능이 저하됨
	시작 정점에서 도달할 수 없는 정점은 탐색하지 않음	찾아낸 경로가 최단 경로가 아닐 수 있음
	BFS보다 탐색 시간이 오래 걸림

 

- 활용방법

BFS	DFS
그래프의 모든 정점 방문	그래프의 모든 정점 방문
최단거리 구하기	경로의 특징 저장(탐색중 장애물이 있는 경우 포함)  → BFS는 경로의 특징을 가지지 못함  → a-b경로에 같은 숫자가 있으면 안될때 등
검색대상의 규모가 크지 않을때	검색대상의 그래프가 아주 클 때
검색 시작 지점부터 찾는 값이 별로 멀지 않을 때 (depth가 얕을 경우)

 

 

- 주의할 점

BFS	DFS
방문 여부 체크 (방문한 정점은 다시 방문하지 않아야 함)  → 자료구조(보통 boolean타입 배열)를 초기화 해야함	방문 여부 체크 (방문한 정점은 다시 방문하지 않아야 함)  → 그래프 내의 순환구조(Cycle) 고려
큐의 적절한 활용  → 반드시 방문여부 체크 후 삽입  → 큐가 비어있는지 확인후 정점 꺼내기	모든 정점을 방문할 수 있도록 시작정점 선택
최단 경로 탐색  → 큐에 정점을 삽입할 때 해당 노드까지의 거리를 기록하는 변수를 사용해야하는 경우도 있음	최단경로를 보장하지 않음  → 최단경로가 필요한 경우 BFS 사용
메모리 공간  → 그래프의 크기가 큰 경우 사용 자제

 

 

 

 

*****

 

 

 

Tomorrow Chapter

# Algorithm

# 의사코드 (Pseudocode)

# 시간 복잡도 (Time Complexity)

# Greedy

# Implementation - Simulation

 

 

 

---

 

 

↓ 이전 글 ↓

[코드스테이츠] 05_15_TIL : 알고리즘/자료구조 _ Tree / Graph

 

↓ 코트스테이츠 부트캠프 관련 글 한번에 보기 ↓

'IT/코드스테이츠 부트캠프' 카테고리의 글 목록