tree_p

the_tree.cpp

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;


vector <int> adj_list[3001];// 인접 리스트 // 이중배열 // 내가 간선리스트로 잘못알려줌 ㅈㅅㅈㅅ;;
vector <int> route;
int root_value;
int check[3001];
int parents[3001];


void print_back_rout(int start_node, int *node_value)
{
	int next = parents[start_node];
	if(next == -1)
		return;
	cout<< node_value[next];

	print_back_rout(next, node_value);

}

void back_dfs(int cur_node, int depth, int *node_value, int &flag)
{
	int parants = parents[cur_node];
	if(parents[cur_node] == -1 && depth - 1 == 0)
	{
		flag = 1;
		// cout << "node_valsue ,routu (" << node_value[cur_node] <<" , "<< route[depth -1]<< ")\n";
		// cout << "depth : " << depth  - 1<< "\n";
	}

	else if(route[depth - 1] == node_value[cur_node])
	{
		// cout <<"node_value , routu ("<<route[depth -1]<< " , " <<node_value[cur_node] << ") \n";
		depth--;
		back_dfs(parants, depth, node_value, flag);
	}
}

void dfs(int cur_node, int pre_node,int *node_value, int depth)
{
	int object_node = route[depth-1];
	if(object_node == node_value[cur_node])
	{
		int flag = 0;
		back_dfs(cur_node, depth, node_value, flag);
		if(flag == 1)
		{
			cout << node_value[cur_node];
			print_back_rout(cur_node, node_value);
		}
	}
	check[cur_node] = 1;
	for(int i = 0; i < (int)adj_list[cur_node].size(); i++)
	{
		int next_node = adj_list[cur_node][i];

		if(check[next_node] == 0)
		{
			parents[next_node] = cur_node;
			// cout << "next_node : " << next_node << "\n";
			dfs(next_node, cur_node, node_value , depth);
		}
	}

}

int main()
{
	int n; // 노드의 갯수;
	int input_count; // 입력 갯숫
	cin >> n;
	cin >> input_count;
	cin >> root_value;
	while(input_count--)
	{
		int from;
		int to;
		cin >> from >> to;
		 // 양방향 그래프이므로 간선 양방향으로 간선리스트 에 할당.
		adj_list[from].push_back(to);
	}

	int *node_value	= new int[n + 1];
	memset(node_value , 0, sizeof(int) * n + 1);

	for(int i = 1; i <= n; i++)
	{
		int value;
		cin >> value;
		node_value[i] = value;// 노드 순서 대로 값을 입력한다 ex 3 4 5 7 5 5 5
	}

	int count_route;

	cin >> count_route;
	int i = count_route;
	while (i--)
	{
		int route_vlaue;
		cin >> route_vlaue;
		route.push_back(route_vlaue);
	}

	// for(int i = 1; i <= n; i++) // 인접 리스트 출력
	// {
	// 	cout << "i : [" << i << "] [ ";
	// 	for(int j = 0; j < (int)adj_list[i].size(); j++)
	// 	{
	// 		cout << adj_list[i][j] << ", ";
	// 	}
	// 	cout << "]";
	// 	cout <<  "\n";
	// }

	// for(auto loop : route)
	// {
	// 	cout << loop << " ";
	// }
	// cout << "\n";

	parents[1] = -1;
	dfs(1,-1, node_value, count_route);

	// for(int i = 0; i <= n; i++)
	// {
	// 	cout << "i : "<< i << " checok: "<< check[i];
	// 	cout << "\n";
	// }

	// for(int i = 0; i <= n; i++)
	// {
	// 	cout << "preoredr i: " << i << " : " <<parents[i];
	// 	cout << "\n";
	// }
}

tree_p.py

from sys import stdin

node, edge, root_num = map(int, stdin.readline().split())
check_dfs = [0] * (node * 2) #dfs 체크
adj_list = [[]for _ in range(node * 2)] #인접리스트
parents = [0] * (node * 2) #부모를 기록하는 리스트

def print_back(start_vertex, node_value_list): #뒤로 돌면서 출력하는 함수
	next = parents[start_vertex]
	if next == -1:
		return;
	print(node_value_list[next], end ="")
	print_back(next, node_value_list)

def back_dfs(cur_vertex, node_value_list, route_list, depth, flag): #뒤로 돌면서 rouet_list = 3 4 5 를 확인하는 함수
	parents_value = parents[cur_vertex]
	if(parents_value == -1 and depth - 1 == 0):
		flag  = 1
		return flag
	elif(node_value_list[cur_vertex] == route_list[depth - 1]):
		depth -= 1
		flag = back_dfs(parents_value, node_value_list, route_list, depth, flag)
		return flag

def dfs(cur_vertex, node_value_list, route_list, route_len): #전체 를 도는 main dfs
	check_dfs[cur_vertex] = 1
	flag  = 0 # flag 의 초기값
	if node_value_list[cur_vertex] == route_list[route_len - 1]:
		#dfs 가 5 를만나면 뒤로 돌아가면서 3 4 5 = route_list  가 맞는 지 확인한다
		#맞으면 now_flag 는 1 이되고 아니면 None 이다
		new_flag= back_dfs(cur_vertex, node_value_list, route_list ,route_len, flag)
		if(new_flag == 1):
			print(node_value_list[cur_vertex], end ="") #route 존재하면 현재 노드 출수
			print_back(cur_vertex, node_value_list) # 부모 따라가면서 뿌리에 닿으면 출력하는 함수
	for i in range (len(adj_list[cur_vertex])):
		next = adj_list[cur_vertex][i] #인접리스트를 활용한 dfs 부분
		if(check_dfs[next] == 0):
			parents[next] = cur_vertex #부모노드를 기록하는 부분
			dfs(next, node_value_list, route_list, route_len)

def main():
	adj_list_input = list()
	i = edge
	while i != 0:
		i -= 1
		adj_list_input.append(list(map(int , stdin.readline().split())))

	for from_node, to_node in adj_list_input:
		adj_list[from_node].append(to_node)

	node_value = list(map(int, stdin.readline().split()))
	node_value.insert(0, 0) #node_value 의 인덱스는 node 번호 , node 번호와 해당 값을 맞추기 위해 맨앞에 0 삽입
							#원래 index 0 = 3, index 1 = 2 -> index 1 = 3 index 2 = 2
	route_len = int(input())
	route_list = list(map(int, stdin.readline().split()))
	parents[1] = -1 #뿌리의 부모는  -1

	dfs(1,node_value, route_list,route_len)

if __name__ == "__main__":
	main()

7 6 3
1 2
1 3
2 4
2 5
3 6
3 7
3 4 5 7 5 5 5
3
3 4 5

입력 정리
간선 갯수, 노드 갯수 , 루트 노드의 값 = 7 6 5
그래프 입력 * 6개
노드 번호 순 값 = 3 4 5 7 5 5 5
찾아야하는 경로 의 길이 = 3
찾아야 하는 경로 = 3 4 5
👍