99클럽 코테 스터디 14일차 TIL + DFS(All Paths From Source to Target)

오늘의 과제

리트코드 Medium으로 분류된 All Paths From Source to Target입니다.

 

어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.

문제

https://leetcode.com/problems/all-paths-from-source-to-target/description/

 

먼저 문제 요구사항 요약입니다.

 

입력으로 방향성 비순환 그래프가 주어지면 0번 노드에서 n-1 노드까지 이동할 수 있는

모든 경로를 반환하면 됩니다.

 

0번부터 n-1번까지의 경로만 탐색하면 되니 DFS를 이용하여 풀었습니다.

 

이전까지의 DFS 문제 풀이와 같은 방식으로 진행해주면 됩니다.

 

대략적인 문제 풀이 방식입니다.

 

1. 현재 방문 경로 추가

2. 현재 노드에서 갈 수 있는 노드 탐색

3. 재귀가 끝나면 다른 경로 탐색을 위해 마지막 노드 제거

4. n - 1에 도착했다면 현재까지의 경로를 result에 추가

 

코드입니다.

 

class Solution {
    List<List<Integer>> result;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        result = new ArrayList<>();
        dfs(new ArrayList<>(), graph, 0);
        return result;
    }

    private void dfs(List<Integer> path, int[][] graph, int level) {
        // 방문한 경로를 추가한다.
        path.add(level);
        // n - 1 노드에 도착했다.
        if (level == graph.length - 1) {
            // n - 1 노드까지의 경로가 담긴 path를 result에 담는다.
            result.add(new ArrayList<>(path));
        } else {
            // 해당 노드에서 이동 가능한 노드로 이동한다.
            for (int node : graph[level]) {
                dfs(path, graph, node);
            }
        }
        // 다른 경로도 탐색해야 하니 마지막에 추가된 노드를 삭제한다.
        path.remove(path.size() - 1);
    }
}

 

배운 점

 

처음 문제를 봤을 때 입력을 이해 못해서 시간을 많이 허비했습니다.

 

분명 노드에서 이동 가능한 경로를 표시해줘야 하는데 [[1, 2], [3], [3], []] 라고 표시되어 있으니

조금 헤맸는데 그냥 단순히 각 인덱스가 노드 번호이고 각 요소들이 이동 가능한 경로였습니다.

 

사실 코드를 봐서 아시겠지만 코테 문제는 구현 자체가 어려운게 아닌

문제가 어떤 것을 원하는지, 어떤 조건이 주어지는지를 이해하고 설계하는 능력이 관건인것 같습니다.

 

문제를 많이 본다고 빨리 이해할 수 있는 능력이 생기는지는 알 수 없지만

중꺽마 마인드로 꾸준하면 좋아지지 않을까 굳게 믿고 갑니다.

 

 

오늘의 한줄평

문해력을 길러야 수학적 사고 또한 빠르게 좋아질 수 있다.