DSA (데이터구조와 알고리즘) 면접 질문 - "DFS가 뭔가요?"

DFS를 다음과 같이 알아보겠다:

- 지난 시간 BFS를 알아보았다. BFS와 차이점은?

- DFS는 어떤 때 쓰고 예시 코드는?

 

2025.02.14 - [개발 관련 기타/알고리즘] - DSA (데이터구조와 알고리즘) 면접 질문 - "BFS가 뭔가요?"

 

BFS와 차이점은?

DFS는 Depth-First Search를 뜻한다. 깊이 우선 탐색이다. 이 방식으로 인해 어떤 차이점이 생기는지 알아보았다.

- 특징으로는 백트래킹 알고리즘에 사용되는 알고리즘이다.

- 한 곳을 해보고, 그 한 곳을 토대로 파생되는 곳 해보고. 그 파생되는 곳 해보고 또 다시 파생되는 곳 해보고. 만약, 더 이상 파생되는게 없다면, 그 전 단계에서 파생된 곳 해보고 하는 식이다.

 

graph:

      A
    / | \
   B  C  D
  / \  |
 E   F G

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'C': ['G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

# graph = dict of lists

 

DFS 방식: LIFO (후입선출) 을 활용한다

1. start 노드로 간다. start 노드를 갔다고 표시한다.

2. 노드에서 갈 수 있는 첫번째 것을 간다. 이때, 간 곳이라면 안간다.

3. 다음 노드에 갔으면 갔다고 표시한다. 그리고 그 노드에서 갈 수 있는 다음 노드로 간다

4. 갈 곳이 없으면 전 노드에서 2를 한다.

 

DFS 사용 자료구조:

- stack

from collections import deque

stack = [] # python에서 stack은 list 사용 가능
stack = deque() # stack을 위해 deque를 사용해도 무방함

# insert
stack.append('A')

# delete
node = stack.pop()

- recursion: 내부적으로 stack으로 동작하는 방식을 사용

def recursion(parameters):
    condition = True
    if condition:
	    return
    recursion(modified_parameters)

 

BFS 비교 메모리 사용량:

- 더 적다: BFS 비교 하였을 때 queue에 집어넣지 않으므로

 

stack과 recursion 비교:

- recursion이 함수 호출 스택에 의해 메모리 사용량이 더 많다

- stack이 함수 호출 오버헤드가 없어 더 빠르다

 

DFS 코드:
- stack: stack을 사용 할 때는 전 단계 노드로 실행 흐름이 직접 가지 않는다. 전 단계 노드에서 이미 방문할 노드들을 stack에 넣었기 때문에, stack 순으로 하나씩 꺼내서 방문하는 방법을 사용한다.

from collections import deque

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'C': ['G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

stack = deque()
visited = set()

start = 'A'
stack.append(start)
visited.add(start)

while stack:
	node = stack.pop()
	print(node)
	for neighbor in reversed(graph[node]):# B부터 먼저 가려고. 보통 왼쪽에서 오른쪽으로 가므로.
	    if neighbor not in visited:
	        stack.append(neighbor)
	        visited.add(neighbor)

- recursion: 갈 수 있는 node 만큼 루프를 돈다

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'C': ['G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

def dfs(node, visited):
    visited.add(node)
    print(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)
    
start = 'A'
visited = set()

dfs('A', visited)

 

DFS 사용하는 때와 예시 코드

특징:

• 최단거리 보장 안됨

사용하는 때:

• 순환탐색
• 백트래킹
  • 한 곳이 안되면 다시 돌아가 다른 곳을 하는데 최적임
    • BFS는 메모리가 비효율적으로 사용됨:
      
      • DFS 어차피 안되는 경로를 따로 저장할 필요가 없음
      • BFS는 추후에 갈 녀석들에 대한 개별 상태들을 기록하고 있어야함. DFS는 상태를 relative하게만 가지고 있으면 됨
• 순열:
• 정의:
  • nPr:
    • n개의 자리가 있을 때 r 명의 사람을 앉힐 수 있는 경우의 수
    • ABC가 앉아 있더라도, ABC와 BCA는 다르다. 옆에 있는 사람이 달라지거나 없너 질 수 있기 때문에.
• graph: 
  • node: 깊이에 따른 완성된 경우의 수 한개
  • edge: 가능한 선택지. visited를 활용.
  • traverse:
    • path: 현재까지 걸었던 길
    • stack: stack에 추가하는 것은 path + 선택지 및 visited 에 대한 상태
    • recursion: 한 단계 들어 갈 때 path + 선택지
    • visited: 이미 순열 만들 때 사용한 것 
    • end: 타겟 r에 대한 순열 경우의 수 1개가 만들어진 경우
• 시간 복잡도:
  • O(n^r):  n * (n-1) * (n-2) * (n-r+1) 번 만큼 계산이 일어난다
• python (recursion and stack):

nums = ['A', 'B', 'C', 'D']
r = 2

# recursion

def dfs_permutation_recursion(nums, r, path, visited, result):
    
    if len(path) == r:
        result.append(path)
    else:
        for num in nums:
            if num not in visited:
                next_visited = visited.copy()
                next_visited.add(num)
                next_path = path + [num]
                dfs_permutation_recursion(nums, r, next_path, next_visited, result)

visited = set()
path = []
result = []

dfs_permutation_recursion(nums, r, path, visited, result)

print(len(result))

# stack

from collections import deque

def dfs_permutation_stack(nums, r):
    
    stack = deque()
    visited = set()
    result = []
    
    init = ([], visited)
    
    stack.append(init)
    
    while stack:
        
        path, visited = stack.pop()
        
        if len(path) == r:
            result.append(path)
        else:
            for num in reversed(nums):
                if num not in visited:
                    next_visited = visited.copy()
                    next_visited.add(num)
                    next_path = path + [num]
                    next_node = (next_path, next_visited)
                    stack.append(next_node)
    return result

result = dfs_permutation_stack(nums, r)
print(len(result))

• 조합:
  • 정의:
    • nCr: n개 중 r개를 선택 할 수 있는 경우의 수
  • graph:
    
    • node: 깊이에 따른 완성된 조합의 경우의 수 한 개
    • edge: 가능한 선택지. index를 활용.
    • traverse: 공집합 (nC0) node에서 출발 해서 r의 증가에 따라 
      • stack: 다음 이어만들 path와 봐야할 index를 넣은 것
      • recursion: 다음 이어만들 path와 봐야할 index를 인수로 넣어서 호출
      • index: 조합은 현재 자신의 index 다음번부터 path를 이어만드는 방식이다
      • end 조건: 타겟 r에 대한 조합 경우 수의 1개가 만들어진 경우
  • 시간복잡도:
    • O(n^r): 최악의 경우 n * (n-1) * (n-2) * (n-r+1) 번 만큼 계산이 일어난다
      
      • 최적의 경우: 6C1 = 6
      • 최악의 경우: 6C6 = 6 * 5 * 4 * 3 * 2 * 1 
  • python (recursion and stack):

# recursion

def dfs_combination_recursion(nums, path, r, index):
    if len(path) == r:
        print(path)
    else:
        for i in range(index, len(nums)):
            dfs_combination_recursion(nums, path + [nums[i]], r, i+1)

nums = ['A', 'B', 'C', 'D']
index = 0
r = 4
path = []

dfs_combination_recursion(nums, path, r, index)

# stack

from collections import deque

def dfs_combination_stack(nums, r):
    stack = deque([])

    init = (0, [])
    stack.append(init)
    
    while stack:
        node = stack.pop()
        index, path = node
        
        if len(path) == r:
            print(path)
        else:
            for i in range(index, len(nums)):
                stack.append((i + 1, path + [nums[i]]))

nums = ['A', 'B', 'C', 'D']
dfs_combination_stack(nums, 3)

• N-Queens:
  • 정의:
    • n 크기의 체스판이 주어졌을 때, n 개의 queen을 서로 공격하지 않도록 각 queen을 어디에 둘 수 있는지 계산하는 알고리즘
  • tree traversal:
    • level: placing another queen as going deeper level
    • branch: placing another queen at different places on a chess board
      • pruning: 기존에 올려둔 queens 를 공격하지 않는지 확인
        • for each queen, 해당 row에 한해서
          • 1: 상하 - queen col 에 의해 안되는 곳
          • 2: 대각선 1 - -45도 대각선 에 의해 안되는 곳: row + col 값이 같다
          • 3: 대각선 2 - 45도 대각선 에 의해 안되는 곳: row - col 값이 같다
          • 좌우 - queen row는 신경안써도 된다. 왜냐하면 row 당 1개만 올리기 때문에.
        • 위 안되는 것들은 저장해서 가져감 (set): queens, diagonals_1, diagonals_2
          • 저장하는 이유: 기존에 계산한 값을 사용, set 사용 시 O(1) 가능함. 매번 queens 루프 돌면서 확인하면 O(n)
    • node: 현시점의 queens 좌표들
    • leaf: 최종적인 n queen의 각 y 좌표
    • end:
      • row index의 size 벗어남: n개의 queen 이기 때문에, 각 row 별 특정 col에는무조건 올려져야 하므로
      • 그리고 한 곳에 올릴수록 row 을 1식 증가 시킬 텐데, index의 size 벗어남은 모든 곳에 올릴 때까지 pruning에 거쳐서 살아남았다는 뜻이므로 성공적인 결과라고 볼 수 있다
  • 시간복잡도:
    • recursion:
      • O(n!): level (row) 당 queen 을 어디에 둘지 선택한다. 이미 둔 곳 제외.
        •  level 1: n 자리, level 2: n-1 자리, level 3: n-2 자리
      • 단, 실제 실행 속도는 pruning에 의해 줄어든다.
        • pruning 시간복잡도:
          • 기존 queens의 col 비교: O(1)
          • 기존 queens에 의한 대각선 비교: O(1) + O(1)
    • stack:
      • O(n!): recursion과 같다.
      • 단, 실제 실행 속도는 pruning에 의해 줄어든다.
  • python :

# recursion

# level: number of queens
# edge: possible queen placement
# node: states
# end: n queens placed. queen is placed at either each row or each col.
# pruning: create checkboard with queens. check availability.
    # row
    # col
    # diagonal

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        results = [] # columns
        queens = []
        cols = set()
        diagonals_1 = set()
        diagonals_2 = set()
        start = 0
        self.backtracking_recursion(n, queens, cols, diagonals_1, diagonals_2, start, results)

        answer = []
        for result in results:
            board = []
            for col in result:
                row = []
                for i in range(n):
                    if col != i:
                        row.append('.')
                    else:
                        row.append('Q')
                board.append(''.join(row))
            answer.append(board)
        return answer

    def backtracking_recursion(self, n, queens, cols, diagonals_1, diagonals_2, row, results) -> List[int]:
        if row == n:
            results.append(queens.copy()) # queens must be copied, or else it will get changed after
            return
        
        for col in range(n):
            # place queen
            if col not in cols:
                diagonal_1 = row + col
                if diagonal_1 not in diagonals_1:
                    diagonal_2 = row - col
                    if diagonal_2 not in diagonals_2:
                        queens.append(col)
                        cols.add(col)
                        diagonals_1.add(diagonal_1)
                        diagonals_2.add(diagonal_2)
                        self.backtracking_recursion(n, queens, cols, diagonals_1, diagonals_2, row + 1, results)
                        queens.pop()
                        cols.remove(col)
                        diagonals_1.remove(diagonal_1)
                        diagonals_2.remove(diagonal_2)

# stack

# edge: next possible queen
# node: queens cols list
# stack: next step을 저장

from collections import deque

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        results = self.dfs_stack(n)

        answer = []
        for result in results:
            board = []
            for col in result:
                row = []
                for i in range(n):
                    if col != i:
                        row.append('.')
                    else:
                        row.append('Q')
                board.append(''.join(row))
            answer.append(board)
        return answer

    def dfs_stack(self, n: int):

        stack = deque()

        result = []

        queens = []
        cols = set()
        diagonals_1 = set()
        diagonals_2 = set()
        row = 0

        start = (queens, cols, diagonals_1, diagonals_2, row)
        stack.append(start)

        while stack:
            node = stack.pop()

            queens, cols, diagonals_1, diagonals_2, row = node
    
            if row == n:
                result.append(queens.copy())
                continue

            for col in range(n):
                if col not in cols:
                    diagonal_1 = row + col
                    if diagonal_1 not in diagonals_1:
                        diagonal_2 = row - col
                        if diagonal_2 not in diagonals_2:
                            queens.append(col)
                            cols.add(col)
                            diagonals_1.add(diagonal_1)
                            diagonals_2.add(diagonal_2)
                            next = (queens.copy(), cols.copy(), diagonals_1.copy(), diagonals_2.copy(), row + 1)
                            stack.append(next)
                            queens.pop()
                            cols.remove(col)
                            diagonals_1.remove(diagonal_1)
                            diagonals_2.remove(diagonal_2)
        return result