공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

[백준 20924][💛4] 트리의 기둥과 가지 (DFS, 트리)

Date:     Updated:

카테고리:

태그:

🚀 난이도

💛 골드 4


🚀 문제

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

image

image

image


🚀 내 풀이

기둥의 길이 / 가지의 최대 길이 이렇게 따로 구해야하기 때문에 기둥 길이를 구하는 재귀, 가지 길이를 구하는 재귀 이렇게 구분 하여 DFS 돌리면 편할 것 같다.

  • 1️⃣ 입력시 인접리스트를 만든다. (무방향인 것 고려하기!)
  • 2️⃣ 기둥 길이를 구하는 DFS 수행
    • 종료 조건
      • “기가 노드”가 등장했을 때 👉 기둥의 끝이자 가지의 시작인 노드.
      • 더 이상 자식이 없을때, 즉 리프 노드에 도달했을 때 👉 기둥에서 리프노드를 만났다는 것은 가지가 없다는 의미이다.
  • 3️⃣ 가지 길이를 구하는 DFS 수행
    • DFS 를 통해 모든 가지를 검사하면서 최대 길이를 업데이트 하면 된다.
    • 종료 조건
      • 리프 노드에 도달했을 때

나는 3 가지 풀이를 제출했는데 사실 로직은 동일하다.

  • 🔥 첫 번째 풀이
    • 3 가지 재귀 함수 사용 : make_tree, find_pole, find_max_branch
    • 입력에서 저장한 인접리스트는 [노드] = { 자식, 부모, 자식 } 이런식이다. 즉, 말그대로 인접했다는 정보만 담고 있을 뿐, 부모와 자식 구분은 되어 있지 않은 것이다. 따라서 make_tree 함수를 통해 루트부터 시작하여 타고 내려가 [부모노드] = { 자식, 자식 } 이렇게 확실히 자식 노드 정보만 담을 수 있도록 새로운 인접 리스트 tree 를 만들어주었고 이걸 find_pole, find_max_branch 에 사용 하였다.
  • 🔥 두 번째 풀이
    • 2 가지 재귀 함수 사용 : find_pole, find_max_branch
    • [노드] = { 자식, 부모, 자식 } 에서 자식만 취하는 방법은, 부모노드는 이미 방문하고 내려왔을테니 방문 체크 bool 배열을 마련해두어 방문하지 않은 노드로만 내려가도록 하면 된다. 방문 했었다면 부모 노드인것이다! 굳이 첫번째 풀이처럼 재귀 한번 더 돌릴 필요 없이 그냥 bool 배열 하나만 마련하면 된다.
  • 🔥 세 번째 풀이
    • 두 번째 풀이의 응용이다. 방문 체크 bool 배열을 사용하지 않고 재귀 함수에 int parent 매개변수를 추가로 두어 호출할 때 현재 노드를 int parent 에 넘긴다. 현재 노드가 다음 재귀에선 부모 노드가 되기 때문이다. 인접리스트에서 parnet와 같지 않은 것에 대해서만 재귀 돌리면 된다.

이런 차이일 뿐이다! 첫 번째 풀이가 재귀함수를 3개 쓰긴하지만 인접리스트를 [부모] = 자식 형태로 정리한 것을 사용하는게 재귀 종료 조건식이 짧아져 더 직관적이고 가독성이 좋다고 생각했다! 채점 결과 두 풀이의 시간 차이를 그닥 없었다. 10 ms 정도…


🔥 첫 번째 풀이 ⭕

tree 배열을 [부모노드] = { 자식, 자식 } 형태로 정리했기에 방문 체크가 전혀 필요하지 않다. 기둥 DFS 경우엔 반복문도 필요 없다. 인접리스트 tree 에 기둥은 자식이 1 개인게 보장되므로.

#include <bits/stdc++.h>

using namespace std;

struct Node { int next, cost; }; // 구조체 안쓰고 cost 정적 이차원 배열 따로 만들어서 사용했는데 메모리 초과가 발생하였다. 안쓰는 공간이 너무 많아져서 그런 듯 하다. 구조체로 바꾸고 jagged array 형태로 바꾸니 메모리 초과는 해결함
vector<vector<Node>> adj_list; // [노드] = { 자식, 부모, 자식 }
vector<vector<Node>> tree; // [부모노드] = { 자식, 자식 }
int Giga, pole, branch; // giga 가 이미 C++ 라이브러리에 있는..건가 보다. giga 라고 하니 모호함 떠서 Giga 라고 해줌 ㅠ

void make_tree(int now, int parent) {
	for (int i = 0; i < adj_list[now].size(); ++i) {
		int next = adj_list[now][i].next;
		if (next != parent) {
			tree[now].push_back(adj_list[now][i]);
			make_tree(next, now);
		}
	}
}

void find_pole(int now, int sum) {
    // 기가 노드를 발견했거나 리프 노드에 도달했을때 (이땐 기가 노드가 없는 경우)
	if (tree[now].size() >= 2 || tree[now].empty()) {
		Giga = now;
		pole = sum;
		return;
	}

    // 기둥은 자식이 1 개
	int next = tree[now][0].next;
	int nextCost = tree[now][0].cost;
	find_pole(next, sum + nextCost);
}

void find_max_branch(int now, int sum) { 
    // 리프노드에 도달
    // 기가 노드가 없는 경우에도 find_max_branch 호출하자마자 바로 이곳에 걸리게 된다. 그래서 자연스럽게 branch 는 0 이 된다.
	if (tree[now].empty()) {
		branch = max(branch, sum);
		return;
	}

	for (int i = 0; i < tree[now].size(); ++i) {
		int next = tree[now][i].next;
		int nextCost = tree[now][i].cost;
		find_max_branch(next, sum + nextCost);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, R;
	cin >> N >> R;

	adj_list.resize(N + 1);
	tree.resize(N + 1);
	for (int i = 1; i <= N - 1; ++i) {
		int node1, node2, cost;
		cin >> node1 >> node2 >> cost;

		adj_list[node1].push_back({ node2, cost });
		adj_list[node2].push_back({ node1, cost });
	}

	make_tree(R, R); 
	find_pole(R, 0);
	find_max_branch(Giga, 0);

	cout << pole << ' ' << branch;
}


🔥 두 번째 풀이 ⭕

이 풀이는 부모 자식 섞인 인접리스트를 그대로 사용한다. 따라서 bool 타입의 visited 배열을 따로 두고 방문체크를 하였다. 방문한적이 있다면 부모 노드!

트리는 사이클이 없는 그래프이다. 따라서 트리를 순회한다면 이미 탐색 완료한 노드는 다른 경로에서 두 번 다시는 방문할 일이 없다. 그러니 다른 여타 DFS 풀이들처럼 visited를 false로 해제하지 않아도 된다.

기둥의 종료 조건문이 좀 더 복잡해졌다. 인접리스트는 부모, 자식 정보가 섞여 있기 때문에 좀 더 세밀하게 조건을 설정해주어야 했다.

  • 기둥 길이 재귀 종료 조건
    • 기가 노드가 존재하는 경우
      • 인접 리스트 크기가 3 이상 (명백하게 자식 노드가 2개 이상임)
      • 인접 리스트 크기가 2 인데 본인이 루트 노드 (이 경우 루트노드가 곧 기가 노드)
    • 기가 노드가 존재하지 않는 경우 (리프 노드에 도달)
      • 인접 리스트 크기가 1 인데 루트 노드는 아님 (그럼 그 1개는 부모노드라는 뜻이므로)
      • 인접 리스트 크기가 0 (이 경우 루트가 곧 리프노드)
#include <bits/stdc++.h>

using namespace std;

int N, R;
struct Node { int next, cost; };
vector<vector<Node>> tree;
vector<bool> visited;
int giga_node, pole, branch;

void find_pole(int now, int totalCost) {
	
	bool giga_exist = tree[now].size() > 2 || (now == R && tree[now].size() == 2);
	bool giga_not_exist = (now != R && tree[now].size() == 1) || (now == R && tree[now].size() == 0);
	if (giga_exist || giga_not_exist) {
		giga_node = now;
		pole = totalCost;
		return;
	}

	for (int i = 0; i < tree[now].size(); ++i) {
		int next = tree[now][i].next;
		int nextCost = tree[now][i].cost;
		if (!visited[next]) {
			visited[next] = true;
			find_pole(next, totalCost + nextCost);
		}
	}
}

void find_max_branch(int now, int totalCost) {

	bool isLeaf = tree[now].size() == 1;
	if (isLeaf) {
		branch = max(branch, totalCost);
		return;
	}

	for (int i = 0; i < tree[now].size(); ++i) {
		int next = tree[now][i].next;
		int nextCost = tree[now][i].cost;
		if (!visited[next]) {
			visited[next] = true;
			find_max_branch(next, totalCost + nextCost);
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> R;

	tree.resize(N + 1);
	visited.resize(N + 1);
	for (int i = 1; i <= N - 1; ++i) {
		int node1, node2, cost;
		cin >> node1 >> node2 >> cost;
		
		tree[node1].push_back({ node2, cost });
		tree[node2].push_back({ node1, cost });
	}
    
    visited[R] = true; // 루트 노드 방문 체크 미리!
	find_pole(R, 0);
	find_max_branch(giga_node, 0);

	cout << pole << ' ' << branch;
}


🔥 세 번째 풀이 ⭕

두 번째 풀이와 비교해서 visited 배열이 사라졌고 재귀 함수에 int parent 가 추가 되었다. 이걸로 방문 체크, 즉 부모 노드인지를 구분한다. giga_parent 도 추가로 필요하다. 가지 DFS 를 진행할 때 기가 노드의 부모도 알아야 기가 노드의 인접 리스트에서 부모 자식을 구분해야 하기 떄문이다.

#include <bits/stdc++.h>

using namespace std;

int N, R;
struct Node { int next, cost; };
vector<vector<Node>> tree;
int giga_node, giga_parent, pole, branch;

void find_pole(int now, int parent, int totalCost) {

	bool giga_exist = tree[now].size() > 2 || (now == R && tree[now].size() == 2);
	bool giga_not_exist = (now != R && tree[now].size() == 1) || (now == R && tree[now].size() == 0);
	if (giga_exist || giga_not_exist) {
		giga_parent = parent; // 기가 노드의 부모도 저장
		giga_node = now;
		pole = totalCost;
		return;
	}

	for (int i = 0; i < tree[now].size(); ++i) {
		int next = tree[now][i].next;
		int nextCost = tree[now][i].cost;
		if (next != parent)
			find_pole(next, now, totalCost + nextCost);
	}
}

void find_max_branch(int now, int parent, int totalCost) {

	bool isLeaf = tree[now].size() == 1;
	if (isLeaf) {
		branch = max(branch, totalCost);
		return;
	}

	for (int i = 0; i < tree[now].size(); ++i) {
		int next = tree[now][i].next;
		int nextCost = tree[now][i].cost;
		if (next != parent)
			find_max_branch(next, now, totalCost + nextCost);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> R;

	tree.resize(N + 1);
	for (int i = 1; i <= N - 1; ++i) {
		int node1, node2, cost;
		cin >> node1 >> node2 >> cost;

		tree[node1].push_back({ node2, cost });
		tree[node2].push_back({ node1, cost });
	}

	find_pole(R, R, 0);  // 루트 노드는 부모가 없으니 루트 노드, 루트 노드로 호출
	find_max_branch(giga_node, giga_parent, 0); // 기가 노드와 기가 노드의 부모

	cout << pole << ' ' << branch;
}

image


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)