코딩 테스트 스터디 - 1주차

1. DFS 구현 방식 (재귀 vs 스택) 비교

재귀로 하는 방법

• 그냥 함수 안에서 또 자기 자신을 계속 부르는 방식으로 내가 지금 뭔가 하고 있다가, 다른 걸 처리하러 가는 느낌.
• 장점 : 코드가 간결하고 생각하는 흐름이랑 비슷해서 이해하기 비교적 쉽다.
• 단점: 너무 깊이 들어가면 스택 오버플로우로 인해 프로그램이 뻗을 수도 있다.

스택을 쓰는 방법

• 내가 직접 stack이라는 상자를 들고 다니면서, 갈 노드를 하나씩 넣고 꺼내는 방식.
• 장점 : 직접 관리하기 때문에 스택 오버플로우 발생 X. 흐름 제어하기 용이.
• 단점 : 구현이 복잡해질 수 있음. 스택을 직접 관리해야해서 코드도 길어지고 귀찮을 수 있음.

2. 그래프

노드들이 간선으로 연결된 구조로, 어떤 것들 사이의 연결 관계를 표현할 때 쓰는 자료구조. 방향 그래프와 무방향 그래프로 나눠진다.

방향 그래프(Directed Graph)

A → B처럼 한쪽 방향만 연결되어 있기 때문에 A에서 B로는 갈 수 있지만, B에서 A로는 못 갈 수도 있음.
ex) 인스타 팔로우, 작업 순서, 웹 링크 etc...

무방향 그래프 (Undirected Graph)

A ↔ B처럼 양쪽으로 연결되어 있어서 A에서 B로 갈 수도 있고, B에서 A로도 갈 수 있음.
ex) 도로 양방향 연결 etc...

방향 그래프에서 사이클 있는지 DFS로 어떻게 확인할까?

→ DFS 돌면서 내가 방문한 노드를 상태를 3개로 나눠 기억한다.

1. 방문안함(Unvisited) → 0
2. 현재 탐색 중(Visiting) → 1
3. 다 끝내고 나옴(Visited) → 2

만약 DFS 돌다가 '지금 탐색 중'인 노드한테 또 가게 되면? 돌고 돈다는 뜻으로 사이클이 있다는 것을 알 수 있음.

3. 백트래킹의 동작 방식

말 그대로 "다시 돌아가기"로 어떤 경로로 계속 가다가 "이건 아닌데?" 싶으면 한 칸 뒤로 돌아가서 다른 길로 가보는 것으로 생각하면 됨.
정확한 의미는 재귀 호출이 종료되면 자동으로 이전 함수 호출로 돌아가는데 이 과정이 바로 백트래킹이며, 이전 상태로 되돌아가며 탐색을 계속한다.

def dfs_path(graph, node, path):
    path.append(node)
    if node == '목표':
        print(path)
    else:
        for neighbor in graph[node]:
            if neighbor not in path:
                dfs_path(graph, neighbor, path)
    path.pop()  # 백트래킹

path.pop()이 백트래킹 동작. 현재 경로에서 노드를 제거하고 이전 분기로 돌아간다. 이를 통해 모든 가능한 경로 탐색 가능