2024-12-10.md

🗓️ 2024-12-10

🐌 스크럼

• 학습 목표 1. 트리의 지름, DFS

💡 새로 배운 내용

1. 카카오테크 코딩테스트 8주차 3번

• 문제 풀이 흐름
  1. 트리 입력 받기
     노드 간 연결 정보를 입력받아 인접 리스트 형태로 저장
     
  2. DFS를 이용해 첫 번째 탐색
     임의의 노드(보통 1번 노드)에서 시작하여 가장 먼 노드를 찾음
     이 과정에서 트리의 "지름 끝 점 중 하나"를 구함
     
  3. DFS를 이용해 두 번째 탐색
     앞에서 찾은 "가장 먼 노드"를 시작점으로 다시 DFS를 수행
     이 탐색의 결과로 "트리의 지름"을 구함
     
  4. 트리의 지름 출력
     두 번째 DFS에서 구한 최대 거리를 출력
     트리의 노드 개수 기준으로 거리에 1을 더해야 지름의 노드 수가 됨
     

• 시간 복잡도
  • DFS는 트리의 모든 노드를 한 번씩 방문하므로 O(N)
  • 두 번의 DFS를 수행하므로 전체 시간 복잡도는 O(2N) = O(N)

// tree의 지름 구하기 (tree, dfs)

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

vector<vector<int>> tree;
vector<bool> visited;

void dfs(int node, int distance, int& maxDistance, int& firstNode) {
visited[node] = true;

    if (distance > maxDistance) {
    	maxDistance = distance;
    	firstNode = node;
    }

    for (auto nextNode:tree[node]) {
    	if(!visited[nextNode]) {
    		dfs(nextNode, distance+1, maxDistance, firstNode);
    	}
    }

}

int main() {
int N;
cin >> N;

    tree.resize(N+1);

    for (int i=0; i<N-1; i++) {
    	int u, v;
    	cin >> u >> v;

    	tree[u].push_back(v);
    	tree[v].push_back(u);
    }

    // 1번째 노드에서 가장 먼 노드 찾고
    int maxDistance = 0, node = 1;
    visited.assign(N+1, false);
    dfs(1, 0, maxDistance, node);

    // 앞에서 나온 가장 먼 노드에서 가장 먼 노드 한 번 더 찾기
    maxDistance = 0;
    visited.assign(N+1, false);
    dfs(node, 0, maxDistance, node);

    cout << maxDistance + 1 << endl;
    return 0;

}

👏🏻 오늘의 회고

• 왜 dfs를 두 번 실행해야 하는지, 트리의 지름이 어떤 알고리즘인지 잘 몰랐었는데 이번 문제를 통해 공부할 수 있었다.

🔗 참고 자료 및 링크

• 트리의 지름 레퍼런스