C++106 [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를 돌리는 것은 비효율적이므로 자기 그룹의 꼭대기에 있는 사람만 비교하는 것이다. 2와 8은 다른 그룹인 것을 알 수 있다. 트리에 값 추가하는 방법 parent[2] = 3; parent[7] = 3; parent[5] = 3; parent[8] = 4; 두 수가 같은 집합인지 알기 위해 필요한 함수 int find_root(int node) { if (parent[node].first == node) return node; //노드의 최적화: 항상 부모를 루트노드로 만듬 return parent[node] = fi.. 2024. 2. 22. [백준][bfs] 7569 토마토 c++ 구현 목차 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 문제 구현 방향 bfs를 이용한 전형적인 문제로 이중 배열를 활용하여 풀었다. 문제 풀이 시 주의점 문제에서 퍼지는 방향을 잘 생각해서 갈 수 있는 범위를 지정해 주어야 한다. 종료 조건을 잘 설정해 주어야 날짜를 올바르게 구할 수 있다. 문제 풀이 예시 입력) 5 3 3 -갈 수 있는 범위의 제한: 앞 뒤를 제외한 방향- 층의 종류: 0층, 1층, 2층 y좌표 .. 2024. 2. 21. [백준][bfs] 트리의 부모 찾기 11725 c++구현 목차 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 제목 문제 구현 방향 이진 트리가 아니기 때문에 인접리스트를 만들어 bfs탐색을 통해 해결해 보았다. 코드 구현 #include #include #include using namespace std; vectortree[100000]; vectorvisit(100000, false); vectorparent(100000, 0); //부모를 저장할 배열 void bfs(int start) { queue q; q.push(start); visit[start] .. 2024. 2. 19. [백준][bfs] 1068 트리 c++ 구현 목차 https://www.acmicpc.net/problem/1068 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다www.acmicpc.net문제 문제 구현 방향이진 트리가 아니기 때문에 인접리스트를 통해서 문제를 접근하였다.삭제는 bfs를 통해 탐색하여 삭제 노드를 표시하는 방법으로 접근했다. 문제 풀이예시 입력)91 6 4 1 3 3 8 8 -13 0 103 2 345 42 5 61 7 867 (단방향 인접 리스트) 그래프와 인접리스트로 표현한 모습이다. 0 103.. 2024. 2. 19. 이전 1 ··· 21 22 23 24 25 26 27 다음 728x90
