[알고리즘] 깊이 우선 탐색 chapter.02

클릭 시 깊이 우선 탐색 chapter.01

깊이 우선 탐색의 기본 개념을 이해하고 난 뒤 문제를 읽어봤는데, 기본 개념으로는 풀 수 없는 문제였다. 그래서 추가 공부를 하게 되었다.

중복 방문을 허용하는 깊이 우선 탐색

chapter.01에서 다뤘던 dfs는 한번 방문한 노드의 경우 바로 탐색에서 제외하는 방식이었는데, 중복 방문을 허용하고 최대 방문 허용 횟수도 지정하는 탐색도 필요한 경우가 있다는 것을 알았다. 여기서 그래프 라는 자료구조가 나오는데, 아직 배우지 못한 개념이다. 챕터 1에서 썼던 트리도 마찬가지긴 한데.. 이제 안 배웠는데 그냥 해야되는 환경에 익숙해졌다. 수월해졌다는 뜻이 아니다. 그냥 내가 처한 환경을 인정한 것이다. 내가 바보라서 어려운 게 아니라 몰라서 어렵다고 생각하면 마음 편하니까 괜찮다.

1. 노드 정의

class Node {
    let value: Int
    var neighbours: [Node]
    var visitCount: Int		// 방문 카운트
    var maxVisits: Int		// 최대 방문 횟수
    
    init(_ value: Int, maxVisits: Int) {
        self.value = value
        self.neighbours = []
        self.visitCount = 0
        self.maxVisits = maxVisits
    }
    
    func addNeighbour(_ node: Node) {
        neighbours.append(node)
    }
    
    // 방문 횟수가 최대 횟수를 넘지 않으면 방문 가능 상태
    func canBeVisited() -> Bool {
        return visitCount < maxVisits
    }
}

2. 그래프 정의 : dfs 함수를 재귀함수로 정의

class Graph {
    var nodes: [Node]
    
    init() {
        self.nodes = []
    }
    
    // dfs 함수
    func dfs(start: Node) {
        // 디버깅용 변수 : 현재 탐색 경로
        var currentPath: [Int] = []
        var visitedNodes: Set<Int> = []
        
        // dfs 재귀
        func dfsRecursive(node: Node) {
            // 노드가 최대 방문 횟수에 도달했는지 여부를 확인
            guard node.canBeVisited() else {
                print("Node \(node.value) has reached at max visits.")
                return
            }

            // 방문 횟수 카운트
            node.visitCount += 1

            // current path에 현재 노드 추가
            currentPath.append(node.value)
            print("Visiting node \(node.value), visit count : \(node.visitCount)/\(node.maxVisits)")
            print("Current path : \(currentPath)")
            
            // 방문한 node 기록
            visitedNodes.insert(node.value)
            
            // 이웃 탐색
            for neighbour in node.neighbours {
                // canBeVisited = true이면 이웃 탐색 진행
                if neighbour.canBeVisited() {
                    dfsRecursive(node: neighbour)
                }
            }
            
            // 탐색 경로에서 마지막 노드 삭제 > 이전 노드로 돌아가 다음 노드를 탐색할 수 있게 함
            currentPath.popLast()
        }

        // dfs 재귀 시작
        dfsRecursive(node: start)
        
        // 결과 출력
        print("\nTotal unique nodes visited : \(visitedNodes.count)")
        print("[Final visit counts]")
        nodes.forEach { print("Node \($0.value) : \($0.visitCount) visits") }
    }
    
    // 그래프에 노드 추가
    func addNode(_ node: Node) {
        nodes.append(node)
    }
}

3. 노드 정의
내가 만들고 싶은 탐색 구조는 다음과 같다.

...ㅋ 그림 진짜 못 그리고 열받는다 아오
하여튼 말로 설명 안해도 그림으로 설명이 될 거라 생각한다.

let node1p = Node(1, maxVisits: 4)
let node1m = Node(-1, maxVisits: 4)
let node2p = Node(2, maxVisits: 4)
let node2m = Node(-2, maxVisits: 4)
let node3p = Node(3, maxVisits: 4)
let node3m = Node(-3, maxVisits: 4)

4. 이웃 정의

node1p.addNeighbour(node2p)
node1p.addNeighbour(node2m)

node1m.addNeighbour(node2p)
node1m.addNeighbour(node2m)

node2p.addNeighbour(node3p)
node2p.addNeighbour(node3m)

node2m.addNeighbour(node3p)
node2m.addNeighbour(node3m)

5. 그래프에 노드를 추가하고 dfs 함수 호출

let graph = Graph()
[node1p, node1m, node2p, node2m, node3p, node3m].forEach { graph.addNode($0) }

graph.dfs(start: node1p)
print()
graph.dfs(start: node1m)

이 출력을 통해 시작점 노드는 한번만 방문이라는 것을 알았다. 나는 1-2-3과 1-2--3이 다른 visitCount일줄 알았다. 마지막 출력문을 보면 구조의 맨 위층 노드는 2의 0제곱, 두번째 층 노드는 2의 1제곱, 세번째 층 노드는 2의 2제곱회의 방문을 카운트하는 것을 알 수 있다. 다음에는 maxVisits를 pow(2, n)를 활용해 지정해야 겠다.

알고리즘 문제 답안 제출은 목요일까지 였는데, 일요일 밤에서야 나는 이 실습을 마쳤다. 사실 처음부터 제출이 가능할 거라고 생각하지 않았기에 못 낸 건 괜찮다. 이제 이걸 활용하여 제출기한이 사흘 지난 문제를 차근차근 풀어보도록 하겠다.