백준/트리8 백준 1922 c++ "네트워크 연결" -PlusUltraCode- https://www.acmicpc.net/problem/1922 [필자 사고]최소 스패닝 트리를 이용하며 쉽게 해결할 수 있다. 필자는 입력 받은 가중치들을 벡터에 오름차순으로 정렬 하였다.**** 실수 조심 >> 그 뒤 start와 end 값이 같으면 무시하고 start 와 end 가 현재 같은 Union인지 아닌지를 판다하여 문제를 해결해 나갔다. 아래는 코드 해설이다.설명크루스칼 알고리즘 개요:크루스칼 알고리즘은 가중치가 있는 그래프에서 **최소 스패닝 트리(MST)**를 구하는 알고리즘 중 하나입니다.먼저 모든 간선을 가중치 순서대로 정렬한 후, 사이클을 만들지 않으면서 최소 가중치 간선을 하나씩 선택하여 트리를 만들어 나갑니다.이를 위해 유니온-파인드(Union-Find) 자료구조를 사용해 사.. 2024. 9. 24. 백준 2644 c++ "촌수계산" -PlusUltraCode- https://www.acmicpc.net/problem/2644 [필자 사고]트리형태로 이루어진 촌수를 계산하라는 문제이다. DFS알고리즘과 BFS알고리즘 둘다 사용 가능한 문제이다.필자는 BFS알고리즘을 선택하였다. 선택된 위치부터 모든 경로의 촌수를 저장하는 식으로 문제를 해결했다.논리상 트리형태이지만 처음 리스트를 생성할때는 arr[parent].push-back(child);arr[child].push_back(parent) 와 같이 양방향 리스트로 만들어야 모든 경로를 저장할 수 있다. 아래는 소스 코드 해설이다. 큐를 사용한 BFS 탐색:BFS 방식은 큐를 이용해 출발 노드(p1)에서 시작하여 목표 노드(p2)까지의 최단 거리를 구하는 알고리즘입니다.myQueue는 탐색할 노드를 저장하는.. 2024. 9. 24. 백준 1991 c++ "트리 순회" -PlusUltraCode- https://www.acmicpc.net/submit/1991 [필자 사고] 전위순회, 중위순회, 후위순회를 묻는 문제이다.전위 순회는 현재 노드부터 왼쪽 자식끝으로 이동후 더이상 이동할 수 없으면 자신과 형제노드를 탐방하고 다시 부모를 탐방하는 방식이다. 중위 순회는 이진 트리 형태로 되어있을 때 줄자를 이용하여 왼쪽부터 이동하여 먼저 줄자에 닿게 되는 부분으로 탐방하는 순서다. 후위 순회는 맨 왼쪽 노드의 형제노드를 탐방 후 그의 왼쪽 노드 와 부모노드를 탐방하는 순서이다. 이 문제에서 핵심은 재귀함수 형태로 왼쪽 끝 노드를 탐방 할 수 있냐 없느냐가 키 포인트이다.필자는 재귀함수구현에 있어서 출력 부분의 위치를 햇갈려 다소 시간이 걸렸다. 아래는 코드 해설이다. validateAlpha 함수.. 2024. 9. 23. 백준 1068 c++ "트리" -PlusUltraCode- https://www.acmicpc.net/problem/1068 [필자 사고]트리의 리프노드를 구하라는 문제이다.마지막에 특정 노드를 삭제할 경우 밑의 자식 노느들 또한 삭제된다. 필자는 리스트형태 및 DFS알고리즘을 통해 트리의 리프 노드를 구하는 식으로 문제를 해결했다. 다만 여기서 조심해야 될 점은 루트노드가 반드시 0이라는 보장이 없다는 점이다.-1의 입력이 1번 2번 idx 3번 idx 일지는 아무도 모르기 때문에 이 부분 실수 없길 바란다. 또한 트리의 계층구조가 있기 때문에 양방향이아닌 단방향으로 리스트를 만들어줘야 된다.아래는 소스코드 해설이다. 1. Input 함수:여기서 목표 노드에서 출발하기 전에 트리의 구조를 큐(arr)에 저장합니다. 각 노드는 부모 노드와 연결된 자식 노드의 .. 2024. 9. 20. 이전 1 2 다음
