그래프 이론
(C++) 백준 9372번 - 상근이의 여행
문제 링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 풀이 상근이가 최소한의 수의 비행기로 모든 나라를 돌아다니는 것은 최소 신장 트리를 순회하는 것과 동일하다. (정점 - 1) 개의 간선이 최소 신장 트리에 존재하므로, 비행기도 (정점 - 1) 개를 타게 된다. #include int t, n, m, a, b; using namespace std; int main(){ cin >> t; while..
(C++) 백준 1368번 - 물대기
문제 링크 : https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 새로운 우물을 파는 것은 새로운 정점을 하나 추가하여 그에 맞는 cost를 가지는 간선을 추가하는 방식으로 진행하였다. Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다. #include #include #include using namespace std; tuple t[100005]; int n, e,..
(C++) 백준 1197번 - 최소 스패닝 트리
문제 링크 : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다. 정렬 시에 가장 처음에 나타난 값을 기준으로 정렬하기에, cost 값을 튜플에 맨 앞에 위치시켜야 한다는 점을 간과하여 오랜 시간을 낭비하기도 했다. #include #include #include using namespace std; ..
(C++) 백준 2252번 - 줄 세우기
문제 링크 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 indegree라는 자신에게 들어오는 간선의 수를 저장하는 배열을 사용하여, indegree가 0인 경우에만 큐에 넣어 출력하는 방식으로 풀이하였다. indegree가 0이 아닌 경우에는 연결된 정점을 방문할 때마다 indegree를 1씩 줄여나가며, 0이 되는 순간 큐에 들어가도록 한다. #include #include using n..
(C++) 백준 1260번 - DFS와 BFS
문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 그래프에서의 DFS와 BFS를 구현하는 문제이다. DFS는 Stack을, BFS는 Queue를 사용해서 풀력 형식에 맞게 그래프의 정점을 하나씩 순회하도록 구현하면 된다. #include #include #include #include using namespace std; vector gp[1002]; int visited[1002]; qu..
(C++) 백준 11724번 - 연결 요소의 개수
문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 방향이 없는 그래프를 BFS 하여 풀이하였다. BFS를 사용하여 하나의 정점부터 차례대로 순회하면 이것들은 하나의 연결 요소가 된다. 그렇기에 출발점을 정점 하나하나로 두고, 방문했는지 여부를 사용하면 연결 요소의 수까지 파악할 수 있다. #include #include using namespace std; vect..