[Swift] [47일차] 797_LEET

핀·2025년 1월 23일

SwiftAlgorithm

목록 보기

50/105

797. All Paths From Source to Target

문제 설명

간선 그래프가 주어진다.

그 그래프를 통해서 0에서 시작해서 n-1까지 도달하기 위한 경로를 다 return

문제풀이

예전에 파이썬으로 문제풀다가 또 오랜만에 보는 문제라 당시엔 쉽게 풀었는데 좀 고전해야만 했다.
1. 처음에 bfs로 해서 큐만들고,,, visited배열만들고, 왔다간 경로 배열을 만들고 뭐 코드가 엄청 불어나서 또 걷잡을 수 없어졌었다.
2. 그냥 다 지우고 dfs 방식으로 틀고 다시 파악하니까 이거 경로배열이 있으면 방문배열이 필요없는 상황이었고,
3. 굳이 그때마다 이게 도달할 수 있는지 없는지를 판단할게 아니라 그냥 되는친구만 넣어주면 되는 것이였다.

최종 코드


class Solution {
    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
        let GOAL = graph.count - 1 // 목적지는 n-1
        var answer = [[Int]]()

        func dfs(_ curr_node: Int, _ path: [Int]) {
            if curr_node == GOAL {
                answer.append(path)
                return
            }
            for node in graph[curr_node] { // 현재 노드에서 갈 수 있는 노드 반복문
                dfs(node, path + [node])
            }
        }

        dfs(0, [0])
        return answer
    }
}

print(Solution().allPathsSourceTarget([[1, 2], [3], [3], []]))

너무 오랜만이라 힌트의 도움을 좀 받은 것 같다. 완성해놓고 나면 진짜 간단한데 너무 사소한데에 꽂혀서 헤매는 것 같다.

ex curr_node를 함수안에서 들어갈 수 있는지 판단해줄지를 많이 고심했던 것 같다.

그래서 사실 중간에 이제 이러면 무한루프뜨겠지?해서 돌렸는데, 통과를 해버려서 오잉?한 상황이었다.

문제를 다시 읽어보니

directed acyclic graph (단방향 그래프)라는 표현이 있어서 굳이 이게 무한루프 돌거라고 예상하지 않아도 되는 것이었다.

만약에 무한루프를 해야한다면 같은 코드를 돌리더라도 예를들어서

Solution().allPathsSourceTarget([[1, 2], [1,3], [3], []])이 돌아간다고 가정해보자 ! 그래프는 아래와 같을 것이다.

그럴때에 대비해서는 다음과 같이 코드를 한줄 추가함으로서 무한루프를 방지할 수 있을 것이다.

if !path.contains(node)   //경로배열에 지금가고자하는 노드가 없어야지만 이동!

class Solution {
    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
        let GOAL = graph.count - 1 // 목적지는 n-1
        var answer = [[Int]]()

        func dfs(_ curr_node: Int, _ path: [Int]) {
            if curr_node == GOAL {
                answer.append(path)
                return
            }
            for node in graph[curr_node] { // 현재 노드에서 갈 수 있는 노드 반복문
                if !path.contains(node) {
                    dfs(node, path + [node])
                }
            }
        }
        dfs(0, [0])
        return answer
    }
}