[개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?)

[deslog]

안녕하세요 핫코더분들, 질문이 하나 있는데요! 모두 문제풀기 전에 이코테책에 있는 예제를 보시나요?
저는 그냥 무턱대고 문제를 풀기 시작하는데요 ㅋㅋㅋㅋㅋㅋ 이번에 올라온 문제를 보니까, 보통 실버 2 이상이고, 골드3까지 있더라구요. 무턱대고 풀고 인터넷 풀이과정을 참고할게 뻔한데, 그러다가 정말 개념까지 다 놓쳐버릴것같아서,,,,, 정리를 해봣슴니다.
별 내용은 없구요,,, 정말 정리본입니다 하하... 그럼,, 많관부 🫶

⚫️ 재귀함수

DFS와 BFS를 이해하기 위해서 재귀를 필수적으로 이해해야한다. 나는 아직 재귀함수를 어떻게 돌려서 결과값을 찾으면 되겟다! 싶은 감이 아직 없다….. 어떻게 다들 이걸 그렇게 빨리빨리 머리회전을 하시는것인지..

재귀함수란, 자기 자신을 다시 호출하는 함수를 의미한다. (쳇 이건 나도 알아)

• 작은문제를 해결하고 큰 문제를 해결하는 것이 재귀 아이디어의 핵심이다.
• 재귀는 반드시, 탈출조건이 있어야 한다.

▪️ 대표 알고리즘 구현해보기

라이브 코딩에서 ‘팩토리얼’ 혹은 ‘피보나치 수열’ 알아요? 그거 구현한번만 해볼래요? 이런식으로 진행되는 경우도 있다. (주변에서 그랬었음!) 그래서 대표적으로 어떻게 구현할 것인지 알아두는 것도 중요할 것 같다.

🔖 팩토리얼 함수 구현하기

1. 반복문으로 구현하기

func factorial(num: Int) -> Int {
    var result = 1

    for i in 2...num {
        result *= i
    }
    return result
}

2. 재귀로 구현하기

   재귀 아이디어는 아래 그림과 같다. 작은 문제들을 먼저 해결해주면서 차례대로 올라오면 된다.

func factorial(num: Int) -> Int {
    if num == 1 {
        return 1
    }

    return num * factorial(num: num-1)
}

🔖 피보나치 수열 구현하기

수열 1, 1, 2, 3, 5,,, 를 구현했고 num에 알고싶은 위치 index를 넣으면 그 수를 알려준다

1. 반복문으로 구현하기

func fibonacci(num: Int) -> Int {
    if num == 1 || num == 2 {
        return num
    }

    var a = 1
    var b = 1
    var result = 0

    for _ in 3...num {
        result = a + b
        a = b
        b = result
    }

    return result
}

2. 재귀로 구현하기

func fibonacci(num: Int) -> Int {
    if num == 1 || num == 2 {
        return num
    }
    return fibonacci(num: num-1) + fibonacci(num: num-2)
}

▪️ 재귀와 반복문의 시간복잡도 (팩토리얼 함수 기준으로 설명)

재귀로 구현이 된다는 의미는, 어쨌든 반복문으로도 구현이 가능하다는 소리다. 즉, 두개의 시간복잡도는 같다. 팩토리얼 함수를 기준으로 시간복잡도를 따져보면, 재귀함수도 결국 n-1번의 팩토리얼 함수를 불러내고, n-1번의 연산을 수행한다. 즉, O(n-1)이라는 소린데, 빅오표기법에서는 상수값을 날리므로 O(n)이다.

▪️ 재귀와 반복문의 공간복잡도 (팩토리얼 함수 기준으로 설명)

for문을 사용했을 경우, for문 내부에서의 i 라는 변수와 result라는 변수 , 총 두 개가 생성된다. 그러므로 O(1)의 공간복잡도를 가진다.

재귀를 사용했을 경우에는, 함수가 불려질때마다 stack에 함수가 쌓이게된다. 만약 num이 10으로 입력됐다면, 총 10번의 factorial 함수가 스택에 쌓이게 되고, 10개의 num 변수가 메모리에 올라가게 된다. 입력하는 n에 따라 n-1개의 변수가 메모리에 올라가므로, O(n)의 공간복잡도를 갖는다.

정리하자면 공간복잡도는 비교적 시간복잡도보다는 중요하지 않지만, 굳이 따져보며자면 메모리 적인 측면에서 재귀는 그닥 효율적이라고 볼 순 없을 것 같다. 재귀는,, 보다 함수를 편하게 표기하고 조금더 효율적인 명시를 위해서 자주 사용된다고 하니,,, 마음껏 재귀를 남발할 순 없겠다.

하지만 이런 재귀의 공간복잡도 문제를 해결할 수 있는 ‘꼬리재귀함수’라는 것도 존재한다고 하니, 꼭 알아보자!

⚫️ DFS

• 깊이 우선 탐색, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

• 스택 자료구조를 이용한다.

• DFS의 동작과정

  1. 탐색시작 노드를 스택에 삽입하고 방문처리
  2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있다면, 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 2번과정을 더이상 수행할 수 없을 때까지 반복한다.

• 예제코드

  func dfs(_ start: Int) {
      visited[start] = true
      print(start, terminator: " ")
      for i in 1..<n+1 {
          if visited[i] == false && matrix[start][i] == 1 {
              dfs(i)
          }
      }
  }

▪️ DFS를 주로 사용하는 경우

• 백트래킹
  • DFS는 깊이 우선으로 탐색하기 때문에, 해가 없는 경우에도 끝까지 탐색하면서 들어갔다가 나온다. 이 경우에는 효율성을 떨어지게 한다. → 지정한 이의의 어느 깊이까지만 탐색하는 조건을 추가해서 못찾으면 빠져나와 다른 경로를 탐색하게 해주는 과정이 필요하다.
• DFS는 최단경로를 찾는다는 보장이 없다. (즉, 최단경로는 BFS!!)
  • 해를 찾으면 DFS는 탐색을 종료하기 때문이다.
• 이동할때마다 가중치가 붙는 탐색은 DFS를 주로 사용한다 → 방문처리를 하기 때문
  • (한번 이동한 경로는 또다시 이동하지 못한다면)
  • 경로의 특징을 저장한다 = 각 경로마다 가중치가 있다.
• 그래프의 모든 정점을 방문해야하는 경우에는, DFS든 BFS든 상관없이 모두 구현이 가능하다.
• 출처: https://duckracoon.tistory.com/entry/DFS와-BFS-각각-사용하는-경우

⚫️ BFS

• 너비우선탐색, 가까운 노드부터 탐색하는 알고리즘이다.

• 큐 자료구조를 이용한다.

• BFS의 동작과정

  1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 해준다.
  2. 큐에서 노드를 꺼내어 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 해준다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

• 예제코드

  func bfs(_ start: Int) {
      var queue: [Int] = []
      visited[start] = true
      queue.append(start)
      
      while !queue.isEmpty {
          var newV = queue.removeFirst() 
          print(newV, terminator: " ")
          
          for i in 1..<n+1 {
              if visited[i] == true && matrix[newV][i] == 1 {
                  queue.append(i)
                  visited[i] = false
              }
          }
          
      }
      
  }

  ⚠️ 주의할 점은, 안그래도 BFS는 모든 노드를 탐색하기 때문에 시간복잡도가 엄청난데, 여기서 removeFirst()까지 해버리면 시간초과가 날 경우가 많다. removeFirst()말고 index로 접근하는 방식이 더 좋은 방식이다.

  • removeFirst()는 O(N)이고, 인덱스로 접근하는 것은 O(1)이다.

▪️ BFS를 주로 사용하는 경우

• 최단경로/수단을 탐색할 때 주로 사용된다.
  • 목적지와 가까운 노드(인접노드)를 순차적으로 탐색을 수행하기 때문이다.
• 모든 노드를 탐색해야하는 경우는, DFS나 BFS 둘다 사용 가능하므로, 편한것을 사용하면 된다.

⚫️ 이코테 예제

1️⃣ 음료수 얼려먹기 (p.149)

💬 나의 풀이

• bfs로 푼다는 것은, 시작점부터 가장 깊숙하게 들어가면 해당함수를 종료한다.
  • 즉, (0, 0)부터 모든 노드를 시작점으로 두고 탐색한다음, 인접한 애들을 계속적으로 봐줘야한다.
• 얼음틀이 생성되면 true를 반환하게 하여 result를 계산해준다.

✅ 정답코드

import Foundation

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0]
let m = nm[1]
var iceFrame = [[Int]]()

for _ in 0..<n {
    iceFrame.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

// 방향키: 상하좌우
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

private func dfs(x: Int, y: Int) -> Bool {

    // 범위 벗어나면 끝
    if x < 0 || y < 0 || x >= n || y >= m {
        return false
    }

    // 방문처리 안된 곳이라면 더 파고들어서 인접 노드 확인
    if iceFrame[x][y] == 0 {
        iceFrame[x][y] = 1
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            dfs(x: nx, y: ny)
        }
        return true
    }
    return false
}

var result = 0
for i in 0..<n {
    for j in 0..<m {
        if dfs(x: i, y: j) {
            result += 1
        }
    }
}

print(result)

⚠️ 여기서 나를 깊게 고민하게 만들었던 점

아니 여기서 dfs를 호출하면, 반환되는 값이 unused인데 어떻게 처리하지? 고민했다. ㅋㅋㅋㅋ 사실 근데, 얼음이 얼마나 크게!! 몇칸을 차지해서 생성되었는지는 중요하지 않다. 그냥 인접된 얼음틀들을 전부 방문처리해주면 되는것! 그래서 dfs를 호출해서 방문처리만 해주고, dfs를 통해 반환되는 return 값은 무시해도 좋다.

어차피 if iceFrame[x][y] == 0 을 통해서 이미 얼음틀은 생겼기 때문에, 몇칸이 되는지는 중요하지 않음!

2️⃣ 미로탈출 (p. 152)

💬 나의 풀이

• 아, 최단 경로를 구하는 문제니까 BFS로 접근하면 되겠구나!
• start지점 기준으로 인접하고, 값이 1인 노드는 전부 queue에 저장해줄거임
• queue에서 하나씩 빼서 확인하는데, 범위가 넘어가면 continue, 갈수없으면 continue, 갈 수 있다면 그 노드의 수를 이전노드의 값 +1 로변경해줌

✅ 정답코드

각 miro의 값을 +1씩해주면서 miro 값 자체를 변경해주는 과정을 기억하자. 이런 유형 좀 많은듯? 단지 번호 매기기 등등…

import Foundation

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0]
let m = nm[1]
var miro = [[Int]]()

for _ in 0..<n {
    miro.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

//상하좌우
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

private func bfs(x: Int, y: Int) -> Int {
    var queue = [(Int, Int)]()
    queue.append((x, y))

    while !queue.isEmpty {
        let temp = queue.removeFirst()
        let x = temp.0
        let y = temp.1

        // 지금 위치에서 상하좌우 돌려서 queue에 넣어줄거임
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]

            // 범위 넘거나 괴물있으면 그냥 패스
            if nx < 0 || nx >= n || ny < 0 || ny >= m {
                continue
            }

            if miro[nx][ny] == 0 {
                continue
            }

            if miro[nx][ny] == 1 {
                miro[nx][ny] = miro[x][y] + 1
                queue.append((nx, ny))
            }
        }
    }
    return miro[n-1][m-1]
}

print(bfs(x: 0, y: 0))

[sunshiningsoo]

블로그에서부터 시작해서 이번 DFS+BFS 정리하신 글까지 모두 정독했습니다😀
저는 문제를 풀 경우에 시간복잡도만 생각하는 경향이 있는데, DFS가 일반 Array보다 공간복잡도에서 안좋을수 있군요..!!
역시,, 어떤 점이 좋으면 어떤 점이 딸리게 되는 그런 공학적 마인드 DFS와 Array의 공간복잡도에서 배워가네요..

생각을 정리해서 글로 작성하는 것 많이 배워갑니다!
내공 냠