[Week4] WIL - DFS BFS 정복기

정글에 들어온지 3주가 넘어가면서 슬슬 공부한 내용을 기록해두는 것에 적응이 되기 시작했다. 밖에 있을때는 가끔 생각나는것만 노션에 끄적이고 말았었는데, 이제는 WIL뿐만 아니라 TIL도 작성하게 되었다. 처음에는 그렇게 부담되는 일이 아닐 수 없었는데 어느새 적응이 되어 벌써 4주차 WIL을 쓰고 있다. 쌓여가는 기록들을 보니 나름 뿌듯하고 좋다. 으하하

 

핵심 역량 평가

역량	달성도	목표
문제해결	75%	백준 실버1 수준의 문제를 AI, 구글링 도움 없이 풀 수 있음.
골드 아래 문제들은 이제 어느 정도 풀어낼 수 있는 것 같다.
설계	90%	최대한 효율적인 코드(시간 복잡도/공간 복잡도 고려)를 짜는 것을 목표로 한다.
여러 문제들을 BFS/DFS 두 가지 방법으로 풀어보면서 최대한 최적의 코드를 짜기 위해 노력했다.
구현	50%	문제당 실패 횟수를 3회 이하로 한다.
시간 초과나 런타임 에러(RecursionError) 때문에 계속 틀린 문제들이 많았다
품질	100%	수요코딩회에서 버그없이 돌아가는 결과물을 만든다.
이번 수요코딩회의 핵심 개념과 게임을 적절하게 섞어 만족스러운 결과물을 도출했다.
유지보수	80%	주석을 통해 명확한 풀이를 기록한다.
과정이 복잡한 내용은 주석을 통해 재학습이 편하도록 했다.
협업	70%	코어타임 뿐만 아니라 팀원들과 적극적인 교류를 한다.
코어타임을 2번으로 늘리는 방법을 택했지만, 그 외의 시간에 알고리즘 관련 소통자체는 아직 부족했던 것 같다. 그래도 수요코딩회 날에는 팀원들과 최대한 소통하며 적극적으로 참여했다.
태도	60%	모르겠는 문제에 대해 절대 AI를 사용한 코드 생성을 하지 않는다.
내 정답말고 도무지 답이 안 떠오르는 문제에서 AI에게 코드 생성을 맡긴 경우가 있었다. 앞으로는 다른 정답을 모색하는 것도 최대한 스스로 해봐야겠다.
AI 활용	100%	맞힌 문제라도 AI에 코드 리뷰를 맡겨 더 최적화된 방법이 있는지를 모색한다.
문제를 해결했어도, 더 좋은 방법이 있는지 AI에게 코드리뷰를 맡겨보았다.
학습 민첩성	80%	수요코딩회에서 React의 VDOM과 Diff 알고리즘 개념을 탑다운 방식으로 빠르게 학습한다.
VDOM과 Diff 알고리즘을 Claude를 통해 빠르게 구현하고, 코드를 직접 뜯어보며 팀원들과 이해한 내용을 소통했다.

 

---

이번 주 학습 메인 테마  -  DFS와 BFS 문제 정복

이전 WIL에서는 인상깊었던 문제를 위주로 학습한 내용을 정리했었다.

하지만 이번주는 문제의 풀이방법이 거의 다 비슷했고, DFS와 BFS의 활용 방법을 공부했던 것이 더 기억에 남아서 학습한 내용을 복습하며 내용들을 정리해보고자 한다.

 

BFS - 너비우선 탐색

가까운 곳부터 차례대로 탐색하는 방식이다.

때문에 최단 거리 문제에 강하다.

 

보통 queue 를 사용해서 푸는 구조이다.

BFS 진행 순서는 다음과 같다.

1. 시작 노드를 큐에 넣고 방문 처리한다.
2. 큐의 앞쪽에서 현재 노드를 하나 꺼낸다.
3. 현재 노드와 연결된 노드들 중에서 아직 방문하지 않은 노드를 모두 방문 처리한 뒤, 큐의 뒤쪽에 넣는다.
4. 큐가 빌 때까지 이 과정을 반복한다.

➡️ 먼저 가까운 노드들을 먼저 처리해야 하니까 큐가 적합하다.

 

💡 deque()는 "반복 가능한 것(iterable)" 을 받아야 한다.
      그래서 초기 값을 넣을 때 queue = deque([start]) 처럼 리스트같은 자료구조로 감싸줘야 한다.

 

방문 여부를 저장해두는 방법은 두 가지가 있다.

 

1. 리스트

visited = [False] * (n + 1)
# vistied[1] -> 1번 노드 방문 여부

if not visited[next_node]:
    visited[next_node] = True

 

2. 집합(set)

visited = set()
visited.add(start)

# 사용 방법
if next_node not in visited:
    visited.add(next_node)

 

- 직관적이지만 리스트에 비해 약간 느리다. 리스트는 인덱스를 알고있으면 바로 해당 주소에 접근할 수 있기 때문이다.

- 그럼에도 set을 사용해야하는 경우는 무슨 경우일까?

 

1) 노드 번호가 정수가 아닐 수도 있다.

# 이러면 리스트에서 인덱스로 접근할 수 없다.
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"]
}

 

2) 노드 번호가 띄엄띄엄 있어도 편하다.

노드가 1, 50, 999 이런식으로 생겼으면 리스트를 비효율적으로 생성해야 한다.

-> visited = [False] * 1000

 

BFS 활용 문제

1. 최단거리 구하기

간선 가중치가 없고, "몇 번 만에 도착", "가장 적은 이동", "최소 횟수" 같은 말이 나오면 BFS가 적합한 문제

• 미로에서 출구까지 최소 칸 수
• 1에서 N까지 가장 적은 연산 횟수
• 시작점에서 각 노드까지의 최소 거리

➡️ BFS는 가까운 것부터 레벨 순서대로 탐색해서 처음 도착한 순간이 최단거리이다!

 

 

2. 퍼져나가는 시뮬레이션

동시에 여러 곳에서 번지거나, "하루가 지날 때마다", "한 칸씩 퍼진다" 같은건 BFS가 적합

• 불 번지기
• 바이러스 확산
• 물 차오르기

➡️ BFS는 시간 단계별 처리가 쉽다.

 

2차원 배열/격자 BFS 문제 템플릿 예시

# BFS (2차원 배열 / 격자)
from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q = deque([(x, y)])
    visited[x][y] = True

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))

 

백준 - 점프왕쩰리_실버4(https://www.acmicpc.net/problem/16173)

백준 - 미로 찾기_실버1(https://www.acmicpc.net/problem/2178)

Leetcode - Number of Islands(https://leetcode.com/problems/number-of-islands/?envType=study-plan-v2&envId=top-interview-150)

 

이차원 배열을 BFS로 탐색해서 주어진 조건을 찾아내는 문제들이 자주 보인다.

BFS 문제 감을 익히는데 아주 큰 도움이 되었다.

 

---

DFS - 깊이 우선 탐색

한 방향으로 끝까지 깊게 들어갔다가, 더 못가면 돌아가서 다른 길을 찾는 방식이다.

경로 탐색, 백트래킹, 트리/그래프 구조 탐색에 자주 사용한다.

주로 스택을 사용하거나, 파이썬에서는 재귀로 많이 구현한다.

➡️ DFS는 가장 나중에 들어간 경로를 먼저 처리하는 LIFO 구조와 잘 맞기 때문이다.

 

동작 흐름은 보통 다음과 같다.

1. 시작 노드 방문
2. 연결된 노드 중 하나로 이동
3. 그 노드에서도 다시 더 깊게 이동
4. 더 이상 갈 곳이 없으면 되돌아옴
5. 안 가본 다른 길 탐색

 

재귀로 구현한 DFS 코드 템플릿

def dfs(graph, start, visited=None):
    """
    깊이 우선 탐색 (재귀)

    Args:
        graph: 그래프 딕셔너리
        start: 현재 정점
        visited: 방문 리스트

    Returns:
        방문 순서 리스트
    """
    # TODO: visited가 None이면 초기화
    if visited is None:
        visited = []

    # TODO: 현재 정점 방문
    visited.append(start)

    # TODO: 인접한 정점들에 대해 재귀
    ## 방문하지 않은 정점이면 재귀 호출
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

    return visited

 

재귀로 구현하면 직관적이라 이해가 쉽고, 코드를 작성하는데도 어려움이 있다. 하지만 스택으로 직접 구현한 DFS가 더 유리한 경우가 많다. 왜냐하면 재귀 DFS는 함수 호출이 계속 일어나서..

• 호출/복귀 오버헤드가 있고
• 파이썬에서는 재귀가 상대적으로 느린 편이고
• 깊어지면 RecursionError가 날 수 있기 때문이다.
  • 실제로 재귀로 풀면 백준과 같은 코드 Solve 웹에서 런타임 에러가 자주 뜬다...!

그래서 입력 한도가 큰 문제에서는 스택으로 구현하는 것이 더 유리한 경우가 많다.

 

스택으로 구현한 DFS 코드 템플릿

def dfs_stack(graph, start):
    visited = []
    stack = [start]

    while stack:
        node = stack.pop()

        if node in visited:
            continue

        visited.append(node)
		
        # 재귀 DFS와 비슷한 방문 순서를 맞추기 위해 reversed를 사용한다
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)

    return visited

 

DFS 활용 문제

1. 경로 존재 여부 / 연결 여부 / 완전 탐색

"갈 수 있는가", "연결되어 있는가", "모든 경우를 뒤져라(정답 후보를 전부 탐색)" 같은 문제들은 DFS가 잘 맞는다.

DFS는 한 방향으로 끝까지 파고들기 좋기 때문이다.

• 이 섬과 저 섬이 연결되어 있는가?
• 그래프에 사이클이 있는가?
• 트리 순회
• 백트래킹으로 모든 경우 찾기

 

2. 경우의 수 만들기

순열, 조합, N-QUEEN, 경로 전부 찾기 같은 문제들은 DFS가 더 자연스럽다

• 경우의 수 문제는 선택을 하나씩 쌓아 완성된 답까지 내려가는 구조
• 한 경로를 끝까지 탐색하고 다시 돌아오는 DFS가 가장 적합
• BFS는 완성된 답 하나를 깊게 만드는 느낌보다, 중간 상태들을 한꺼번에 관리하는 느낌이라 경우의 수 생성에는 덜 직관적

 

 

DFS, BFS 공통 활용 문제

👉 도달 가능한지만 필요한 경우

 

트리/그래프를 그냥 한 번 훑는 거면 두 가지 방법 모두 사용 가능하다! 이럴 때는..

• 최단거리도 구해야함 -> BFS
• 그냥 갈 수만 있으면 됨 -> BFS, DFS 아무거나

---

수요 코딩회 - Virtual DOM과 Diff 알고리즘 구현

4주차 수요 코딩회 주제는 React의 핵심 개념인 Virtual DOM과 Diff 알고리즘 구현하기였다. Virtual DOM이 어떠한 이유로 구상된 개념인지를 중점적으로 공부하였고, Diff 알고리즘과 VNODE 객체 생성 코드를 이해하기 위해 코드를 직접 뜯어보는 과정을 거쳤다. 팀원들과 공부를 마치고 각자 맡은 개념을 설명하는 시간을 가졌고, 나는 그 중 VNODE를 생성하는 코드를 맡아서 설명했다.

 

개념적인 내용들은 별도의 글로 정리해두었다 🙂‍↕️

2026.03.24 - [Frontend] - React 렌더링의 핵심: Virtual DOM과 Diff 알고리즘

React 렌더링의 핵심: Virtual DOM과 Diff 알고리즘

 

 

내가 설명을 맡은 부분은 크게 두 가지 함수를 가지고 있다.

function domToVNode(domNode) { }
// 실제 DOM 노드 하나를 받아서 VNode(또는 문자열)로 변환한다.

function createNode(vNode) { }
// VNode를 받아서 실제 DOM 노드를 만들어서 반환한다.

 

domToVNode는 실제 DOM을 읽어 Virtual DOM 형태로 추상화하는 함수이고, createNode는 Virtual DOM을 바탕으로 실제 DOM 노드를 생성하는 함수이다. 즉, 두 함수는 DOM과 VNode 사이를 서로 반대 방향으로 변환하는 역할을 한다.

 

domToVode는 브라우저의 실제 DOM 노드를 받아 {type(태그명), props(속성, class 등등..), children(자식 노드 배열)} 형태의 가벼운 JavaScript 객체(VNode)로 변환하는데, 이때 자식 노드들도 domToVNode를 재귀적으로 호출하여 트리 전체를 빠짐없이 변환한다.

 

createNode는 그 반대로 VNode를 받아 실제 DOM 노드를 만들어 반환하며, 마찬가지로 자식 VNode들에 대해 createNode를 재귀적으로 호출하여 트리 전체를 그대로 복원한다.

 

학습한 내용을 시각적으로 확인할 수 있는 게임 '개발자 키우기'를 만들었다.

 

'검 키우기'라는 게임을 모티브로 '개발자 키우기'라는 게임을 만들어서 학습한 내용을 검증했다. 버튼을 누르면 TEST AREA가 변하고, PATCH 버튼을 누르면 변경된 VNODE가 생성된다. PATCH 패널에는 변경된 내용만 간략하게 출력되고, REAL AREA에 실제로 렌더링한다. 

 

어쩌다보니 3주 연속으로 발표를 맡아서 진행하고 있는데 하다보니 슬슬 발표에 여유가 생기기 시작했다. 여유가 생기니 발표할 때 내가 말하고자 하는 바를 더 명확하게 할 수 있게되었고 이로 인해 코치님께 발표 칭찬을 받았다! 😎

도전을 위해 들어온 정글에서 내가 부족했던 역량을 서서히 채워나가는 느낌이 들어서 기분이 매우 좋았다. 앞으로도 실패를 두려워하지 않기로..!