[코딩테스트 일지 - 99클럽] 8일차 - All Paths From Source to Target

코딩 테스트 준비 일지 8 일차

• 응시 사이트 : LeetCode

• 문제 : All Paths From Source to Target

• 난이도 : 중하

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

 Constraints:

• n == graph.length

• 2 <= n <= 15

• 0 <= graph[i][j] < n

• graph[i][j] != i (i.e., there will be no self-loops).

• All the elements of graph[i] are unique.

• The input graph is guaranteed to be a DAG.

문제 풀이 접근

이 문제는 N개의 노드 데이터를 넘겨주고, 목적지 (마지막으로 넘겨준 노드의 값) 까지의 모든 경로를 어떤 순서로든 리턴하면 되는 문제다.

먼저 이 문제를 해결하기 위해 알고리즘 선택을 할 필요가 있었는데, 나는 모든 경로를 반환해야 한다는 점에서 완전탐색으로 하는 방식을 확인했고, 최단 경로를 탐색하기 좋은 BFS보다 DFS 재귀 구현방식이 더 익숙하기도해서 DFS 재귀 방식을 선택했다. DFS 스택으로 구현할 수 도 있을텐데, 익숙하지 않기도 하고, 재귀 돌려서 본인의 노드를 넘겨주는걸 더 편하게 생각해서 DFS 재귀 방식으로 진행했다.

물론 이 문제의 경우 Graph 클래스를 작성해도 쉽게 풀릴 것 같다고 생각하고, 트리방식으로 생각하고 해도 될 것 같긴하다 .

내가 푼 문제의 플로우는 아래와 같다.
1. 데이터 int[][] 형식의 2차원 배열로 넘어가니 map 이라는 변수를 만들어서 내가 컨트롤하기 쉬운 데이터로 바꾼다. ( 공간 복잡도 잡아먹는다고 쳐도 쓰기 쉬운게 우선이라고 생각하여 이렇게 처리 )
2. 넘어온 데이터의 순서가 곧 노드의 번호다 "n nodes labeled from 0 to n - 1 "
3. 내가 쓰기 쉬운형태로 매핑을 한 후 DFS를 돌려준다.
4. DFS 내부 함수 내가 지나온 경로를 수집해준다.
5. 수집하면서 내가 방문했었는지 잘 체크해서 수집하고, 목적지에 도달하면 수집했던 경로를 List로 넣어주고 내 저장 리스트의 인덱스를 하나 올려준다.

정답 작성 코드 ( C# )

public class Solution {
    const int s_iMaxNodeCount = 25;
    public static int s_ipathIndex = 0;
    public static int s_iGoalPos = 0;

    public static List<List<int>> maps = new List<List<int>>();

    public static Stack<int> recordPath = new Stack<int>();

   public IList<IList<int>> AllPathsSourceTarget(int[][] graph){
maps.Clear();
recordPath.Clear();
s_ipathIndex = 0;
IList<IList<int>> resultList = new List<IList<int>>();
resultList.Clear(); int NodeCount = graph.GetLength(0);
 s_iGoalPos = NodeCount - 1; // 목적지

 for (int i = 0; i &lt; NodeCount; ++i)
 {
     maps.Add(new List&lt;int&gt;()); // 0 은 0 라벨 노드
     var mapsIndex = i;

     for (int j = 0; j &lt; graph[i].Length; ++j)
     {
         var edge = graph[i][j];
         maps[mapsIndex].Add(edge);
     }
 }
 // 맵 매핑 완료

 bool[] isVisit = new bool[s_iMaxNodeCount];
 for (int i = 0; i &lt; s_iMaxNodeCount; ++i)
 {
     isVisit[i] = false;
 }

 DFS(ref resultList, 0, ref isVisit);
 return resultList;}     public void DFS(ref IList&lt;IList&lt;int&gt;&gt; result, int currentNode, ref bool[] isVisit){
if (isVisit[currentNode] == true)
{
if (recordPath.Count > 0) recordPath.Pop();
return; // 방문했다면 종료
}  isVisit[currentNode] = true;
  recordPath.Push(currentNode);

  if (result.Count &lt;= s_ipathIndex)
      result.Add(new List&lt;int&gt;());

  if (currentNode == s_iGoalPos)
  {
      result[s_ipathIndex].Clear();

      for (int i = recordPath.Count - 1; i &gt;= 0; --i)
      {
          var node = recordPath.ElementAt(i);
          result[s_ipathIndex].Add(node);
      }

      ++s_ipathIndex;
      return;
  }

  for (int i = 0; i &lt; maps[currentNode].Count; ++i)
  {
      var node = maps[currentNode][i];

      DFS(ref result, node, ref isVisit);
      isVisit[node] = false;
      recordPath.Pop();
  }}}

코드 결과

프로젝트에서 바로 돌릴 수 있는 코드 ( C# )

    internal class Program
{
public class Graph
{    } // 그래프 풀이도 가능할 것 같다.

    // Q

    const int s_iMaxNodeCount = 20;
    public static int s_ipathIndex = 0;
    public static int s_iGoalPos = 0;

    public static List<List<int>> maps = new List<List<int>>();
    public static Stack<int> recordPath = new Stack<int>();

    static void Main(string[] args)
    {
        int[][] graph = new int[][]
        {
            new int[] { 1, 2 , },
            new int[] { 3 },
            new int[] { 3 },
            new int[] {}
        };



        Program mm = new Program();
        mm.AllPathsSourceTarget(graph);

        int[][] graph2 = new int[][]{
new int[] { 4, 3 , 1},
new int[] { 3, 2, 4 },
new int[] { 3 },
new int[] { 4} ,
new int[] {} ,
};        mm.AllPathsSourceTarget(graph2);

    }
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph)
    {
        maps.Clear();
        recordPath.Clear();
        s_ipathIndex = 0;
        IList<IList<int>> resultList = new List<IList<int>>();
        resultList.Clear();

        int NodeCount = graph.GetLength(0);
        s_iGoalPos = NodeCount - 1; // 목적지

        for (int i = 0; i < NodeCount; ++i)
        {
            maps.Add(new List<int>()); // 0 은 0 라벨 노드
            var mapsIndex = i;

            for (int j = 0; j < graph[i].Length; ++j)
            {
                var edge = graph[i][j];
                maps[mapsIndex].Add(edge);
            }
        }
        // 맵 매핑 완료

        bool[] isVisit = new bool[s_iMaxNodeCount];
        for (int i = 0; i < s_iMaxNodeCount; ++i)
        {
            isVisit[i] = false;
        }

        DFS(ref resultList, 0, ref isVisit);
        return resultList;
    }


    public void DFS(ref IList<IList<int>> result, int currentNode, ref bool[] isVisit)
    {
        if (isVisit[currentNode] == true)
        {
            if (recordPath.Count > 0) recordPath.Pop();
            return; // 방문했다면 종료
        }

        isVisit[currentNode] = true;
        recordPath.Push(currentNode);

        if (result.Count <= s_ipathIndex)
            result.Add(new List<int>());

        if (currentNode == s_iGoalPos)
        {
            result[s_ipathIndex].Clear();

            for (int i = recordPath.Count - 1; i >= 0; --i)
            {
                var node = recordPath.ElementAt(i);
                result[s_ipathIndex].Add(node);
            }

            ++s_ipathIndex;
            return;
        }

        for (int i = 0; i < maps[currentNode].Count; ++i)
        {
            var node = maps[currentNode][i];

            DFS(ref result, node, ref isVisit);
            isVisit[node] = false;
            recordPath.Pop();
        }
    }
}</code></pre><p></p><h2>** LeetCode 에서 문제 풀때는 절대로 전역 변수를 초기화하여 사용하던지 되도록 사용하지 말자.</h2><p></p><p></p><p></p>