https://www.acmicpc.net/problem/2252알고리즘 분류 : 그래프 이론, 위상 정렬, 방향 비순환 그래프❓문제🔅해석위상정렬을 이용하여 풀이한다. 위상정렬은 비순회 방향 그래프에서 정점을 정렬하는 방식이며, 동일한 우선순위를 가진 작업들이 여러 가지 방법으로 나열될 수 있기 때문에 여러 개의 정렬 결과가 나올 수 있다. // input4 24 23 1 1. indegree 계산 및 indegree 배열 중에서 0인 노드를 Queue에 담는다. 2. Queue에서 pop를 하고, 3(pop 한 값)과 연결된 노드에 indegree를 하나 감소시킨다. 3. Queue에서 pop를 하고, 4(pop 한 값)와 연결된 노드에 indegree를 하나 감소시킨다. 4. Queue가 빌 ..
https://www.acmicpc.net/problem/3830알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find 알고리즘으로 해결한다. 부모와 가중치를 함께 저장하기 위해 Node class를 정의한다. // TestCase34 7! 1 2 100? 2 3! 2 3 100? 2 3? 1 3! 4 3 150? 4 1 1. Initialize 2. "! 1 2 100" find를 통해 서로의 부모가 같은지 확인하고 같지 않다면, a의 부모를 b의 부모로 변경하여 하나로 합친다. 3. "? 2 3"2과 3의 부모를 확인한다. 2의 parent(=2) != 3의 parent(=3) 이므로 "UNKNOWN"를 반환한다. 4. " ! 2 3 100" 5. "? 2 3"2과 3의 부모를 확인..
https://www.acmicpc.net/problem/1717알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find의 기초 문제이다. Union 연산은 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산이다.먼저 두 원소가 같은 집합인지 확인하고 같은 집합이 아니라면 하나로 합친다. 보통 같은 집합을 확인하는 과정은 부모의 번호를 기재하여 확인한다.Find 연산은 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환한다. 문제의 예시를 아래와 같이 가정한다.//input7 40 1 31 1 70 7 61 1 3 1. 7 4n개의 집합을 생성한다. 각 집합의 부모는 자신을 가르키고있다. 2. 0 1 3union1과 3에 대해 parent를 확인하고 같..
