[Swift] [59일차] 1557_LEET 단방향 노드

1557. Minimum Number of Vertices to Reach All Nodes

문제 설명

1. 단방향 노드 그래프가 주어진다.
2. 모든 노드 방문하기 위한 시작점 노드를 반환하라
3. 0에서 [0,1,2,5]를 방문할 수 있지만, 3은 방문 못하기 때문에 [0,3]이 반환될 것이다.

---

문제 접근

1. 일단 단방향 그래프이다보니까 간선끼리 딕셔너리로 해당 위치에서 갈 수 있는 노드들을 정리해줬고.
2. 그것을 순회하면서 visited에 해당 위치에서 갈 수 있는곳을 찍어보게끔 dfs를 활용해주었다.

class Solution {
    func initializeVisited(visited: [Bool]) -> [Bool] {
        return
            visited.map { _ in false }
    }

    func findSmallestSetOfVertices(_ n: Int, _ edges: [[Int]]) -> [Int] {
        var graph = [Int: [Int]]()
        for i in 0 ..< n {
            graph[i] = []
        }

        for edge in edges {
            graph[edge[0]]!.append(edge[1])
        }

        var visited = Array(repeating: false, count: n)
        func dfs(visited: inout [Bool], current: Int) {
            visited[current] = true // 현재 노드 방문 처리

            for element in graph[current]! {
                if !visited[element] { // 방문하지 않은 노드라면
                    dfs(
                        visited: &visited,
                        current: element
                    ) // 재귀 호출로 방문 처리
                }
            }
        }
        var answer = [Int: [Int]]()
        for i in 0 ..< n {
            dfs(visited: &visited, current: i)
            let answers = visited.enumerated().compactMap {
                idx, value in value ? idx : nil
            }
            answer[i] = answers
            visited = initializeVisited(visited: visited)
        }
        print(answer)

        return [1]
    }
}

근데 이렇게 하고 나니까 오잉? 이제

[3: [2, 3, 4, 5], 1: [1], 4: [2, 4, 5], 0: [0, 1, 2, 5], 5: [5], 2: [2, 5]] 이렇게 나오는데 어찌해야하지? 또 이거 다 돌면은 너무 시간초과일 것 같은데..해서 멈추고 한참을 고민했던 것 같다.
그냥 내가 임의로 봤을때는 이게 내가 도달할 수 없는 친구가 답에 포함이 되는 것 같은데, 그 생각자체가 모호하다고 느껴서 이렇게 좀 헤맷던 것 같다.

0,3이 답이어야하는데, 보시다시피 0,3인덱스가 0 진입차수 임을 알 수 있다. 이걸 어떻게 구했냐면..

[0, 1, 2, 0, 1, 1]

class Solution {
    func findSmallestSetOfVertices(_ n: Int, _ edges: [[Int]]) -> [Int] {
        var answer = Array(repeating: 0, count: n)

        for item in edges {
            answer[item[1]] += 1
        }
        print(answer)
        return [1]
    }
}

그냥 도착지점에 없는 친구를 솎아준것이다. 이제 인덱스가 0인친구만 추출해서 담아주면 끝날 듯 ??

class Solution {
    func findSmallestSetOfVertices(_ n: Int, _ edges: [[Int]]) -> [Int] {
        var answer = Array(repeating: 0, count: n)

        for item in edges {
            answer[item[1]] += 1
        }

        return answer.enumerated().compactMap { index, value in
            value == 0 ? index : nil
        }
    }
}

위에서 한 뻘짓이 어이없긴한데, 아래처럼 이렇게 값이 0인친구를 한줄로 솎아내줄 수 있는 방법을 활용해보는 계기가 되었다.

        return answer.enumerated().compactMap { index, value in
            value == 0 ? index : nil
        }

좀 효율적으로 푼것같은데 1등은 아니라, 이거보다 2배이상빠른 사람의 코드를 한번 살펴보았다.

---

타인의코드

class Solution {
    func findSmallestSetOfVertices(_ n: Int, _ edges: [[Int]]) -> [Int] {
        var inBound = Array(repeating: false, count: n)
        for edge in edges {
            inBound[edge[1]] = true
        }

        var result: [Int] = []
        for i in 0..<n {
            if !inBound[i] {
                result.append(i)
            }
        }

        return result
    }
}

실상은 동일한데, 별다른 compactMap해서 이걸 분리하는 공정과정을 거치기보다 그냥 바로 append(i)로 추가 과정을 줄인것이었고, 전체를 둘러보니까 다 진입차수로서 해결해준 것을 볼 수 있었다.