해당 글에서는 텀 프로젝트 문제를 Python을 이용해 풀이하고자 한다. 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.net 원래는 이 문제를 풀 생각이 아니었지만, 아래에 있는 Union-Find를 통해 무방향 그래프의 사이클을 구하는 알고리즘에 대해 공부하다가, 방향 그래프에서 사이클을 구하는 방법이 궁금해져 찾아보다가 해당 문제를 풀게 됐다. [알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기1️⃣ 유니온 파인드란?Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로..
1️⃣ 유니온 파인드란?Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 아래와 같이 루트 노드를 찾고(find), 연결된 두 노드를 합치는(union) 연산으로 이루어져 있다.def find(parent, x): # 부모 찾기 if parent[x] != x: parent[x] = find(parent, parent[x]) # 루트 노드가 아닌 경우, 재귀호출을 통해 루트 노드를 찾음 return parent[x]def union(parent, x, y): # 합치기 x = find(parent, x) y = find(parent, y) if x 2️⃣ 유니온 파인드로..
1. BFS란? BFS란 루트 노드(Node)에서 시작하여 인접한 노드를 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 이때 한 번 방문한 정점은 다시 방문하지 않는다. 노드 사이의 최단 경로를 구하고자 할 때, 혹은 임의의 경로를 찾고자 할 때 BFS를 이용한다. 2. BFS를 코드로 구현하려면? 1️⃣ 시작하는 정점을 큐에 삽입하여 방문했다는 표시를 남긴다. 2️⃣ 큐의 제일 앞에 있는 원소를 삭제한 후, 해당 원소에 연결돼 있으면서 아직 방문하지 않은 정점을 큐에 삽입한다. 3️⃣ 큐가 비어있을 때까지 2️⃣를 반복한다. 이때 모든 정점(Node)을 한 번, 모든 간선(Edge)을 두 번씩 방..
1. 그래프(Graph)란? 그래프란 실제 세계의 현상이나 사물의 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용한다. 위 이미지에서 A, B, C, D, E는 정점에 해당하며 각 정점들을 잇는 선은 간선에 해당한다. 2. 그래프 관련 용어 📌 주요 용어 노드(Node): 위치를 말하며, 정점(Vertex)라고도 함 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선임(Link 또는 branch라고도 함) 인점 정점(Adjacent Vertex): 간선으로 직접 연결된 정점(또는 노드) 📌 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진..
