위상정렬3 [백준] 2637 장난감 조립 풀이 Java, 위상 정렬 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net ★ 위상 정렬(Topological Sort)을 잘 모르면 아래 게시글을 보고 오는걸 추천드립니다. 위상 정렬(Topological sort) BFS,DFS 비순환 방향 그래프 DAG (Directed Acyclic Graph) 사이클이 없는 방향 그래프 위상 정렬(Topological sort) 모든 간선(u,v)에 대해 먼저 오는 정점 순서로 정렬이 된다. (u가 v보다 먼저 오면 u->v) 그래프가 DA.. sunrise-min... 2022. 7. 18. [백준] 2252 줄 세우기 풀이 Java, 위상 정렬 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ★ 위상 정렬(Topological Sort)를 잘 모르면 아래 게시글을 보고 오는걸 추천드립니다. 위상 정렬(Topological sort) BFS,DFS 비순환 방향 그래프 DAG (Directed Acyclic Graph) 사이클이 없는 방향 그래프 위상 정렬(Topological sort) 모든 간선(u,v)에 대해 먼저 오는 정점 순서로 정렬이 된다. (u가 v보다 먼저 오면 u->v) 그래프가 DA.. sun.. 2022. 7. 17. 위상 정렬(Topological sort) BFS,DFS 비순환 방향 그래프 DAG (Directed Acyclic Graph) 사이클이 없는 방향 그래프 위상 정렬(Topological sort) 모든 간선(u,v)에 대해 먼저 오는 정점 순서로 정렬이 된다. (u가 v보다 먼저 오면 u->v) 그래프가 DAG인 경우만 가능한데 그 이유는 그래프에 사이클이 있으면 u가 먼저인지 v가 먼저인지 알 수 없기 때문이다. 대표적인 예로 대학교 선수과목이 있다. 위 그림을 보면 하나의 DAG에서 하나 이상의 위상정렬 결과가 나올 수 있으며, 왼쪽에서 오른쪽으로 향하는 단방향이다. 구현은 BFS(in-degree), DFS 둘 다 가능하다. * 참고 - 진입차수 (Indegree) : 특정 노드로 들어오는 간선의 개수 - 진출차수 (Outdegree) : 특정 노드에서.. 2022. 7. 17. 이전 1 다음 반응형
