[자료구조] 트리, DFS(깊이우선탐색), BFS(넓이우선탐색)

트리

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조.

 

자료구조는 크게 비선형구조, 선형구조로 구분됩니다.

 

선형구조(리스트,스택,큐)는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형구조는 표현에 초점이 맞춰져 있습니다.

 

이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다.

 

페이스북을 예시로 들어볼게요! 제가 친구 "제니"를 알고 있고, "로제"와 친합니다.

그리고 "로제"는 트와이스 "사나"를 안다고 하면, 저는 "사나"와 2촌 관계라고 말할 수 있겠죠!

            로제 - 사나
             ⎜       
      제니 - 르탄

르탄이는 연결 관계를 가진 데이터, 노드입니다!
르탄과 제니는 간선으로 연결되어 있습니다.
르탄과 로제는 인접 노드 입니다!

 

 

 

그래프에서 사용되는 용어

• 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
• 간선(Edge): 노드 간의 관계를 표시한 선.
• 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

 

 

그래프는 유방향 그래프와 무방향 그래프 두가지가 있습니다.

 

유방향 그래프(Directed Graph): 방향이 있는 간선을 갖습니다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있습니다. (ex. 팔로잉-팔로워 관계)

무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖습니다. (ex. 서로 일촌관계)

 

 

 

트리의 표현방법

 

이런 그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있습니다!

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현

2) 인접 리스트(Adjacnecy List): (링크드) 리스트로 그래프의 연결 관계를 표현 더 쉽게 표기하기 위해서 각 노드들에 번호를 매겨보겠습니다!

 

제니를 0, 르탄을 1, 로제를 2, 사나를 3 라고 하겠습니다.

 

          2 - 3
          ⎜       
      0 - 1

1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

➡️ 간선 3개!

이걸 배열로 표현하면 다음과 같습니다!
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

2. 이번에는 인접 리스트로 표현해보겠습니다!
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다.

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 

 

이 두 방식의 차이

바로 시간 VS 공간 입니다!

 

인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있습니다.

그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 합니다.

 

인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 합니다.

따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 합니다.

대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간을 사용하면 됩니다.

 

주로 인접 리스트로 훨씬 많이 표현한다.(공간복잡도도 훨씬 적으므로)

하지만, 때로는 배열이 문제풀이에 더 적합할 수도 있긴 하다.

 

 

---

 

DFS

Depth First Search 입니다. 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다.

이 말만 들어서는 방법이 안 떠오르니까, 한 번 구체적으로 실행 과정을 적어보겠습니다!

 

- 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.

- 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.

- 위 과정을 반복한다.

1, 2, 5, 6, 7, 3, 4 순서

 

 

테스트 코드

from dfs_bfs.prac import dfs_recursive, dfs_stack


assert dfs_recursive(1, []) == [1, 2, 5, 6, 7, 3, 4]
assert dfs_stack(1) == [1, 4, 3, 5, 7, 6, 2] # 오른쪽 부터 감

# DFS에 왼쪽, 오른쪽 순서는 중요하지 않음

 

Python 구현 코드

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}

# 재귀적으로 구현 # input 1. 내가 지금 방문한 노드 2. 내가 여태까지 방문한 노드 리스트
def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited

#파이썬으로 구현
def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.(후입선출)
        top = stack.pop()
        visited.append(top)
        # (가장 최근에 방문한 노드 기준으로)인접 노드를 방문한다.
        for adj in graph[top]: # top=1 일 경우 2,3,4 -> 다음 top은 4부터 (후입선출)
            if adj not in visited:
                stack.append(adj)

    return visited

 

💡 재귀적으로 코드를 구현할 경우 가장 중요한 것은

1. 반복되는 부분이 어디인지 파악

2. 종료 시점이 언제인지 파악

---

 

섬의 개수

 

Python stack

def island_dfs_stack(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
        	# 섬이 아니면 pass
            if grid[row][col] != '1':
                continue

            cnt += 1
            # 섬의 좌표 스택에 넣음
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                grid[x][y] = '0'
                # 해당 좌표의 상하좌우 확인
                for i in range(4):
                	# new x, new y, 새 좌표
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # 배열 행,열의 범위 넘을 경우 or 1이 아니여서 방문 가치가 없을때
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    stack.append((nx, ny))
    return cnt


assert island_dfs_stack(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_stack(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

 

 

recursive

def island_dfs_recursive(grid):
    if not grid or not grid[0]:
        return 0
        
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    m = len(grid)
    n = len(grid[0])
    cnt = 0

    def dfs_recursive(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return

        # DFS 탐색의 실제 구현
        # 특정 좌표에서 시작하여 상하좌우 네 방향으로 재귀적으로 탐색하면서 
        # 연결된 모든 '1'을 '0'으로 바꿔서 방문했음을 표시
      
        grid[r][c] = '0' # 방문처리
        for i in range(4):
            dfs_recursive(r + dx[i], c + dy[i])
            
        # 해당 함수의 실행을 중단하고 호출한 위치로 돌아가도록 합니다.(생략가능)
        return
	
    
    # 전체 그리드를 순회하며, 아직 방문하지 않은 '1'(섬)을 발견했을 때 새로운 DFS 탐색을 시작
    # 모든 섬을 개별적으로 탐색하고 세는 역할
    for r in range(m):
        for c in range(n):
            node = grid[r][c]
            if node != '1':
                continue

            cnt += 1
            dfs_recursive(r, c)

    return cnt


assert island_dfs_recursive(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_recursive(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

---

 

BFS(너비 우선 탐색)

DFS 와 BFS 의 차이점 

DFS 는 탐색하는 원소를 최대한 깊게 따라가야 합니다.

이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 됩니다. → 그래서 스택을 썼죠!

 

BFS 는 현재 인접한 노드 먼저 방문해야 합니다.

이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다.

가장 처음에 넣은 노드들..? → 큐를 이용하면 BFS 를 구현할 수 있습니다!

 

BFS 구현 방법

1. 루트 노드를 큐에 넣는다.

2. 현재 큐의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가 비면 탐색을 종료한다.

 

BFS 구현

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start):
	# 방문했다고 표시
    visited = [start]
    # 큐에 넣어줌
    q = deque([start])

	# q가 빌 때까지 반복
    while q:
    	# 제일 앞에 있는 녀석 꺼냄
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited


assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]

 

 

섬의 개수 (Python)

2차열 배열로 주어진 지도에서 섬의 개수를 구하기

https://leetcode.com/problems/number-of-islands/description/

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

def island_bfs(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0 # 섬의 개수

    for row in range(rows):
        for col in range(cols):
			# 1이 아니라면 그냥 pass        
            if grid[row][col] != '1':
                continue
			
            # 1이라면 섬의 개수 카운트
            cnt += 1
            q = deque([(row, col)])
			
            # 섬(q)이 비어있지 않는 동안 반복
            while q:
            	# 제일 처음 입력된 점을 꺼냄
                x, y = q.popleft()
                # 4방향 돌며 신규 좌표 검색
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    grid[nx][ny] = '0'
                    q.append((nx, ny))
    return cnt


assert island_bfs(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_bfs(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

 

 

관련 문제

https://www.acmicpc.net/problem/1260

 

---

DFS와 BFS의 차이점 요약

1. 탐색 방식:
   • DFS: 가능한 깊은 곳까지 탐색하고, 더 이상 갈 곳이 없으면 되돌아옵니다.
   • BFS: 한 레벨의 모든 노드를 탐색한 후, 다음 레벨로 넘어갑니다.
2. 자료 구조:
   • DFS: 재귀 호출 스택을 사용하거나 명시적으로 스택을 사용하여 구현합니다.
   • BFS: 큐를 사용하여 구현합니다.
3. 사용 용도:
   • DFS: 경로 탐색, 사이클 검출 등에 유용합니다.
   • BFS: 최단 경로 탐색 등에 유용합니다.