99클럽 코테 스터디 11일차 TIL + queue, DFS

 

🔗  LeetCode - 1302.All Paths from Source to Target

오늘은 아주 조금 수월했는데 왜 되는 지 모르겠지만 통과한 감이 있어 다시 살펴봤다.

일단 이번 문제는 DAG(Directed Acyclic Graph)를 끝 노드까지 도착할 수 있는 경로를 다 찾는 것이었다. 

DFS를 쓰면 해결될거 같았지만 속도랑 메모리도 신경쓰고 싶어서 queue를 사용했다. 

INPUT : 배열, 각 인덱스가 노드 번호이고 그 내부 배열은 그 노드와 연결된 노드들이다. 

OUPUT: 처음부터 끝 노드까지 순서에 맞게 나열되어 있어야 한다. 2차원 배열

 

일단 첫번째 배열은 따로 처리해 줬다. 시작 노드 이므로 여기에서 OUTPUT 배열을 하나씩 배정해 줬다. 그리고 이 노드를 queue에 넣었다. 

 

그 다음에는 계속해서 queue에서 노드를 꺼내 그 노드와 연결되어 있는 노드를 찾아 배열에 하나씩 append 시켜줬는데 여러개의 노드와 연결되어 있는 경우 OUTPUT 배열 맨 뒤에 새롭게 배열을 할당 해 줬다. 그리고 맨 끝 노드에 도달할 경우 queue에 다시 들어가지 않게 했다. 

 

끝 노드에 도달하지 못하고 끝나는 경로는 삭제해 줬다. 

 

from collections import deque


class Solution:
    def allPathsSourceTarget(self, graph):
        answer = []
        queue = deque()
        max_node = len(graph) - 1

        # 시작점 처리
        for node_idx, node_num in enumerate(graph[0]):
            answer.append([0, node_num])
            if node_num and (node_num != max_node):
                queue.append((node_num, node_idx))
        while queue:
            node_num, node_idx = queue.popleft()
            if graph[node_num]:
                if len(graph[node_num]) == 1:
                    answer[node_idx].append(graph[node_num][0])
                    if max_node != graph[node_num][0]:
                        queue.append((graph[node_num][0], node_idx))
                else:
                    temp = answer[node_idx][:]
                    for idx, node in enumerate(graph[node_num]):
                        if not idx:
                            answer[node_idx].append(node)
                            if max_node != node:
                                queue.append((node, node_idx))
                        else:
                            answer.append(temp + [node])
                            if max_node != node:
                                queue.append((node, len(answer) - 1))
        for ans in answer:
            if ans[-1] != len(graph) - 1:
                answer.remove(ans)
        return answer
        
sol = Solution()
print(sol.allPathsSourceTarget([[1,2],[3],[3],[]])) # [[0,1,3],[0,2,3]]
print(sol.allPathsSourceTarget([[4,3,1],[3,2,4],[3],[4],[]])) # [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
print(sol.allPathsSourceTarget([[2],[],[1]])) # [[0, 2]]
print(sol.allPathsSourceTarget([[2],[3],[1],[]])) # [[0,2,1,3]]