[코딩테스트 일지 - 99클럽] 8일차 - All Paths From Source to Target
코딩 테스트 준비 일지 8 일차
응시 사이트 : LeetCode
난이도 : 중하
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.length2 <= n <= 150 <= graph[i][j] < ngraph[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 < 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();
}}}코드 결과
프로젝트에서 바로 돌릴 수 있는 코드 ( 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>