목록위상정렬 (4)
넘치게 채우기
https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/leetcode - All Ancestros of a Node in a Directed Acyclic Graph문제 유형 : 위상 정렬문제 난이도 : Medium 문제You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).You are also given a 2D integer array edges, where edges[..
https://leetcode.com/problems/minimum-height-trees/description/ Leetcode - Minimum Height Trees 문제 유형 : bfs / 위상 정렬 문제 난이도 : Medium 문제 A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi]..
https://leetcode.com/problems/parallel-courses-iii/description/ Parallel Courses III - LeetCode Can you solve this real interview question? Parallel Courses III - You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] den leetcode.com 문제 유형 : 위상 정렬 문제 난이도 : Hard 문제 Y..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/ujynY/btstCXHk2n6/J7ErqDrmRaNQnhBe3bdta1/img.png)
순서가 정해져 있는 일련의 알고리즘을 수행해야 할 때 사용되는 알고리즘이다. '사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것' 이다. 대표적으로 선수학습 과목 등의 예시가 있다. 진입차수와 진출차수 진입차수(indegree): 특정 노드로 들어오는 간선의 개수(노드로 오기 전의 조건) 진출차수(outdegree): 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정 반복: 큐에서 원소를 꺼내서 그 노드가 향하는 노드의 진입차수를 1 낮추기(그 간선 방문처리) 진입차수가 0이 된 노드를 큐에 넣기 위상 정렬 알고리즘의 예시 1. 진입차수가 0인 노드부터 큐에 넣고 시작한다. 큐에서 요소를 하나 꺼낸다. 꺼내진 요..