2021년 07월 03일 백준 6005번 Cow Pinball (S1)

※ 이 글은 그래프 탐색을 이해했다는 것을 전제 하에 쓰였습니다.
이 문제는 DFS(깊이우선탐색)을 연습하는게 딱 좋은 맵이라고 생각한다. 영어라고 겁먹을 필요없다.
우리에게는 파파고라는 좋은 친구가 있으니까

영어싫어

우리 파파고가 말해준 문제를 약간 요약했을때 이 문제는 저 사진에 나와있는 피라미드로 되어있는 숫자들이 보일것이다. 그래서 맨위의 숫자부터 밑으로 한층씩 내려오는데 이때 자신의 위치에서 바로 왼쪽, 오른쪽 밖에 갈 수가 없다. 그렇게 끝까지 내려왔을때의 합이 가장 큰 경우에서 그 합을 출력하면 되는것이다.
입력으로는 첫번째로 몇층으로 할건지 받고
그이후 피라미드가 만들어졌을때의 갯수 만큼의 숫자를 입력받는다.
출력은 가장 큰 합을 출력한다.
예시로

못그려서 죄송합니다

저 원을 노드라하고 빨간선을 간선이라고 했을때 맨 위에 있는 노드로 부터 시작해서 점점 탐색을 하는데 만약 탐색을 하던 도중 노드에서 외부 노드로 향하는 간선의 갯수가 0일때를 가장 피라미드의 밑부분까지 왔다고 판단하여 지금까지 지나온 경로를 합으로 더하는 방식으로 코드를 짰다.

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

int Num = 0;
int* answer;
int Real_answer = 0;
int N;

typedef struct Node {
	int score = 0;
	vector<int> adj;
} Node;

vector<Node> x;
int real_box = 0;
void DFS(int num, int a) {
	answer[a] = x[num].score;
	if (x[num].adj.size() == 0) {
		for (int i = 0; i < N; i++) {
			real_box += answer[i];
		}
		if (Real_answer < real_box) {
			Real_answer = real_box;
			
		}
		real_box = 0;
		return;
	}
	for (int i = 0; i < x[num].adj.size(); i++) {
		DFS(x[num].adj[i], a + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	answer = new int[N];
	for (int i = N; i >= 1; i--) {
		Num = Num + i;

	}
	for (int i = 0; i < N; i++) {
		answer[i] = 0;
	}
	x.resize(Num);
	int as = 1; 
	int ad = 0;
	for (int i = 0; i < Num; i++) {
		if (ad == as) {
			ad = 0;
			as++;
		}
		cin >> x[i].score;
		if (as < N) {
			x[i].adj.push_back(i + as);
			x[i].adj.push_back(i + as + 1);
		}
		ad++;
	}
	DFS(0, 0);
	cout << Real_answer;
	return 0;
}

이 코드는 처음 짰을 당시 보여주기 용으로 짠 코드가 아니기에 보기에 다소 불편한 구조들이 많다. ex) 변수명

DFS 기초 문제이기 때문에 방식만 안다면 쉬울 것 이므로 코드를 보기보다는 방식만 알아둬도 푸는데 지장이 없다.