2026.01.26 트리& 이진 트리 문제풀이 (백준 1240번, 9934번)

오늘의 문제입니다.

 

 

첫 줄에는 노드의 수 N과 알고자하는 쌍의 수 M을 입력합니다.

그 다음 줄부터는 두 노드와 노드 사이의 거리를 N-1개의 줄에 거쳐 입력하고, M개의 줄에 걸쳐 거리를 알고자하는 노드를 입력합니다. 출력에서는 M개의 줄에 걸쳐 알고자했던 두 노드 사이의 거리를 출력합니다.

 

우선 입력받은 N과 두 노드 사이의 거리를 활용해 트리를 구현하고, 두 노드 사이의 거리를 구해야겠습니다.

 

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N,M;
	cin>>N>>M;
	
	//2차원 배열
	vector<vector<pair<int, int> > >  vec(N+1);
	for(int i=0;i<N-1;i++){
		int node1, node2, d;
		cin>>node1>>node2>>d;
		
		//무방향 그래프
		vec[node1].push_back({node2, d});
		vec[node2].push_back({node1, d});
	}
	
	while(M--){
		int u,v;   //정점과 간선
		cin>>u>>v;
		
		vector<int> distance(N+1, -1);   //거리 배열, -1로 초기화, N+1은 인덱스 맞추기
		queue<int> queue;
		
		distance[u] =0;
		queue.push(u);
		
		while(!queue.empty()){
			int a=queue.front();  //큐의 맨 앞을 a로 두고, 삭제
			queue.pop();
			
			if(a==v) break;
			
			for(auto[newx,w]:vec[a]){
				if(distance[newx]!=-1) continue;   
				
				distance[newx]=distance[a]+w;   //누적하기 
				queue.push(newx);
				}
		}
		
		cout<<distance[v]<<'\n';
	}


	return 0;
}

 

 

 

 

 

 

 

 

 

다음 문제입니다.

 

입력 받은 K과 방문 순서를 활용해 이진트리를 만들고, K개의 줄에 거쳐 이진트리를 출력해내는 문제입니다.

이진트리를 성질을 잘 생각해서 저장해주는게 중요할 것 같습니다.

방문순서가 left-node-right으로 중위 순회 방식으므로 이를 참고해서 이진트리를 복원 후 출력해주면 되겠네요.

전에 풀어본 문제라서 가볍게 풀어보겠습니다.

 

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

vector<int> array;
vector<vector<int>> A;

void mid(int left, int right, int d){
	if(left>right) return;
	
	int m=(left+right)/2;
	A[d].push_back(array[m]);
	
	mid(left, m-1, d+1);  //왼쪽으로 내려가기
	mid(m+1, right, d+1);  //오른쪽으로 내려가기
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int K;  //트리 높이
	cin>>K;
	
	int n = (1 << K) - 1;   //2^K

	
	array.resize(n);
	for(int i=0;i<n;i++) cin>>array[i];
	
	A.resize(K);
	mid(0, n-1, 0);
	
	for(int i=0;i<K;i++){
		for(int x: A[i]) cout<<x<<' ';
		cout<<'\n';
	}
	
	
}

 

중간에 int n=2^K -1; 로 표기를 했더니 런타임 에러가 나서 C++ 형식에 맞게 int n = (1 << K) - 1;로 변경해주었습니다.