[BOJ, C++]#13325_이진 트리, 이진 트리, 포화 이진 트리, DFS, 재귀 DFS

2024. 8. 22. 18:02· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 이진트리
  4. 2. DFS
  5. 3. 현재 정점 기준 왼쪽 서브트리의 최단 경로와 오른쪽 서브트리의 최단 경로 비교
  6. #3. 코드

#1. 문제

https://www.acmicpc.net/problem/13325

 


 

#2. 풀이

 

1. 이진트리

 

[자료구조]#5_트리

[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다.  Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의

webddevys.tistory.com

이진트리는 트리 자료구조의 한 종류로, 각 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하인 트리 자료구조입니다. 따라서, 이진트리의 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가지며, 부모-자식 관계가 하위 레벨에서도 순환적으로 반복되는 계층 구조를 형성해, 전체 트리의 각 서브트리도 모두 이진트리가 됩니다.

 

2. DFS

 

[자료구조]#6_그래프

#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와

webddevys.tistory.com

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 노드로부터 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색을 합니다. 일반적으로, DFS는 재구 호출 혹은 스택 자료구조를 활용해 구현합니다.

 

3. 현재 정점 기준 왼쪽 서브트리의 최단 경로와 오른쪽 서브트리의 최단 경로 비교

  1. 먼저, 힙 구현에 활용되는 배열 인덱싱 방법(부모 = 2/i, 왼쪽 자식 = 2*i, 오른쪽 자식 = 2*i+1)을 고려하여, 배열에 각 간선의 가중치를 저장합니다.
  2. 재귀 호출 DFS를 구현합니다.
  3. 먼저, 종료 조건은 현재 노드가 자식 노드가 없는 단말 노드일 경우 탐색을 종료하고, 간선의 가중치를 결과 값에 더한 뒤 그 값을 반환합니다.
  4. 다음으로, 왼쪽 자식 노드와 오른쪽 자식 노드에 대한 재귀호출, 중복 계산을 방지하기 위해 두 결과 값을 뺀 절댓값에 현재 노드의 가중치 값을 더해 결과 값에 더해줍니다.
  5. 마지막으로, 현재 노드의 가중치 값 + 왼쪽 혹은 오른쪽 자식 노드의 결과 값 중 최대가 되는 값(최대 경로 값을 갖는 경로)을 더해주고, 이를 반환해 줍니다. 
  6. 말이 조금 복잡하지만, 현재 노드의 자식 노드(왼쪽/. 오른쪽) 중 그 경로 값이 최대가 되는 값을 결과 값으로 반환해 주는 동시에, 중복 계산을 방지하기 위해 왼쪽과 오른쪽 경로의 경로 값을 빼주어 현재 간선의 가중치에 더해주고 이를 결과 값에 반영해 줍니다.

 


 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/13325
*   @문제: 가중치 포화 이진 트리에서 루트로부터 모든 리프 노드의 경로에서 에지들의 가중치 증가를 통해 모든 경로의 거리 값을 최소 값으로 통일.
*   @설명
        1. 높이 n, 노드 갯수 2^(n+1) - 1개, 리프 노드 갯수 2ⁿ개
        2. 부모 = i/2, 왼쪽 2*i. 오른쪽 2*i+1
        3. 현재 노드를 시작으로 왼쪽/오른쪽 자식 노드를 통하는 경로의 최대 경로는 곧 최대 값을 갖는 어느 한 경로입니다.
        현재 노드를 기점으로 왼쪽 서브트리의 총 경로 값이 아닙니다!
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int K, ans;
vector<int> tree;

int dfs(int cur, const int& size)
{
    //@리프 노드
    if(cur*2 >= size)
    {
        ans+= tree[cur];
        return tree[cur];
    }

    //@왼쪽 자식 노드
    int leftChild = dfs(2*cur, size);
    //@오른쪽 자식 노드
    int rightChild = dfs(2*cur+1, size);

    //@현재 가중치 + 두 경로 중 '최대 값'으로 업데이트 된 경로의 증가된 값
    ans += tree[cur] + abs(leftChild-rightChild);

    return tree[cur] + max(leftChild, rightChild);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> K;

    //@총 노드 개수, 2^(K+1)-1
    int n = (1<<(K+1)) -1;
    tree.resize(n+1, 0);

    for(int i=2; i<=n; ++i)
    {
        cin >> tree[i];
    }

    //@DFS 수행
    dfs(1, n);

    cout << ans;

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ, C++]#2156_포도주 시식, DP, 동적 프로그래밍, 동적 계획법  (1) 2024.08.28
[BOJ, C++]#5972_택배 배송, 다익스트라, 길 찾기 알고리즘, 최단 경로 알고리즘, 무 방향 그래프  (0) 2024.08.22
[BOJ알고리즘, C++]#2504_괄호의 값, 스택, stack  (0) 2024.08.08
[BOJ]#17431_단어 뒤집기 2, string, stack  (0) 2024.08.02
[BOJ알고리즘, C++]#3190_뱀, deque, map  (1) 2024.07.03
  1. #1. 문제
  2. #2. 풀이
  3. 1. 이진트리
  4. 2. DFS
  5. 3. 현재 정점 기준 왼쪽 서브트리의 최단 경로와 오른쪽 서브트리의 최단 경로 비교
  6. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ, C++]#2156_포도주 시식, DP, 동적 프로그래밍, 동적 계획법
  • [BOJ, C++]#5972_택배 배송, 다익스트라, 길 찾기 알고리즘, 최단 경로 알고리즘, 무 방향 그래프
  • [BOJ알고리즘, C++]#2504_괄호의 값, 스택, stack
  • [BOJ]#17431_단어 뒤집기 2, string, stack
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 알고리즘
  • dfs
  • DP
  • unreal
  • C++
  • Effective C++
  • 디자인 패턴
  • 우선순위 큐
  • BOJ
  • Unreal Blueprint
  • BFS
  • 정렬
  • 그래프
  • 트리
  • 최단 경로
  • 개발
  • stl
  • 기술 질문
  • programmers
  • set

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ, C++]#13325_이진 트리, 이진 트리, 포화 이진 트리, DFS, 재귀 DFS
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.