1. 위상정렬? 2. 방법 어떠한 노드의 관점에서 그 노드로 들어오는 간선의 수를 진입차수라고 한다. 그리고 이러한 진입 차수가 0인 노드가 항상 시작 노드가 된다. 기본적인 알고리즘은 이러한 시작노드들을 큐에 넣고, 시작노드들과 연결되어 있는 다음 순서의 노드들 사이에 간선들을 없애며, 그 과정에서 새롭게 진입차수가 0이된 노드들을 다시 큐에 넣는 방식으로 진행된다. 3. 소스코드 #include #include #include #include using namespace std; // 부무노드 개수 저장 int parent[32001]; // togo[i]에는 i가 향하는 정점들을 저장 vector togo[32001]; queue q; int main() { int N, M; cin >> N >> ..

*다익스트라의 정석 문제 #include #include #include #include #include #define INF 987654321 #define max_v 20001 #define max_e 300001 using namespace std; int V, E; // graph[i]={j,w} : i 에서 j노드로 가는 가중치 w vector graph[max_v]; int dist[max_v]; // distance[j] : 출발노드에서 j노드까지의 거리, 초기엔 모두 INF void dijst(int start) { for (int i = 1; i w) { dist[toNode] = w; pq.push({ w, toNode }); } } } return; } int main() { cin...

트리순회 트리를 순회할 때 어떤 노드를 먼저 탐색하느냐에 따라 전위,중위,후위로 나눌 수 있다. 각각의 순회를 알아 본다. 전위순회 부모 -> 왼쪽자식 -> 오른쪽자식 더이상 부모노드가 없을때 그 다음 노드(왼쪽자식)을 탐색한다 중위순회 왼쪽자식 -> 부모 -> 오른쪽자식 더이상 왼쪽자식이 없을때 그다음 노드(부모)를 탐색한다 후위순회 왼쪽자식 -> 오른쪽자식 -> 부모 그다음 왼쪽자식이 없을때 그다음 노드(오른쪽자식)을 탐색한다 *출처 : https://hongku.tistory.com/160 예시코드 (백준 1991 트리순회) def preorder(N): global graph if N in graph: print(N, end="") preorder(graph[N][0]) preorder(graph..

1. 풀이 (1) 입력이 하나의 그래프임이 보장될때 트리일 조건은 (노드개수-1)==(간선개수)가 된다. (2) 간선개수가 0인것은 빈트리이므로 이것역시 트리이다. 2. 소스코드 #include #include #include #include using namespace std; int main() { int num1, num2; string ans; int t = 1; while (1) { cin >> num1 >> num2; if (num1 < 0) { break; } // test case else { vector graph; set s; // 입력 while (1) { if (num1 == 0 and num2 == 0) { break; } else { graph.push_back(make_pair..

1. 함수의 구성 유니온 파인드는 find와 union 두가지 함수로 구성이 된다. (1) find는 그래프에서 루트노드를 찾아주는 함수이다. int find(int x) { if (parent[x] == x) { return x; } else { return parent[x] = find(parent[x]); } } (2) union은 서로 연결되어 있지 않은 그래프를 연결시키는 함수이다. void Union(int x, int y){ x = find(x); y = find(y); if(x!=y){ parent[y] = x; } } 2. 함수의 사용 유니온 파인드는 아래의 두가지 경우에 사용할 수 있다. (1) 그래프가 연결되어 있는지 확인할 때 (ex [boj]1717_집합의 표현) 어떤 두 노드의 ..

dfs(stack)를 이용하여 그래프에서 사이클이 있는지 확인할 수 있다. 이때 그래프가 유향일때와 무향일때 방법이 각각 다르다. ​ 1. 무향그래프 (1) stack #싸이클인지 확인 def isCycle(L): visitedN=[] myL=list(L) stack=deque([myL[0][0]]) while stack: nowN=stack.pop() #싸이클인지 확인 if nowN in stack: #(if nowN in visitedN도 된다!) return True for i in myL: if nowN in i: if nowN==i[0]: other=i[1] else: other=i[0] if other not in visitedN: stack.append(other) visitedN.appen..