728x90
⭐️ 난이도
Gold 2
⭐️ 문제
https://www.acmicpc.net/problem/2250
⭐️ Idea flow
문제를 해결하려면 우선 각 노드가 격자에서 몇 번째 행, 몇 번째 열인지 알아야 한다.
문제를 읽어보면 먼저 "같은 레벨(level)에 있는 노드는 같은 행에 위치한다"라는 말이 있다. 따라서 행을 구하는 것은 별 문제가 없다.
(level이 곧 행이 되기 때문에)
문제는 몇 번째 열인지 구하는 것인데, 문제에서 주어진 규칙과 위 그림을 보면 제일 left-most node가 제일 작은 열이고, right-most node가 제일 마지막 열임을 알 수 있다.
좀 더 자세히 보면 순회랑 연관이 있음을 알 수 있는데, left subtree들이 먼저 제일 작은 열들로 설정이 되고 나서 root가 설정이 되고, 그 다음 right subtree들의 열이 설정됨을 알 수 있다.
이와 같은 방식은 in-order traversal(중위순회)이며, 그 말은 즉 주어진 트리를 중위 순회하면서 차례대로 열 번호를 부여하면 된다는 뜻이다.
2차원 vector인 grid 변수를 선언하고 [i][k]에서 [i]는 해당 노드의 level을, [k]는 몇 번째 열인지를 저장한다.
모든 노드의 행과 열의 정보를 저장했다면, grid를 level마다 모두 정렬하고 너비를 구하면서 최댓값을 갱신한다.
그리고 구한 최대 너비와 최대 너비가 있는 level을 출력한다.
⭐️ Code
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;
// 2250 - 트리의 높이와 너비
struct Node{
int left, right;
};
int n, col = 1, result_width, result_level;
vector<Node> graph; // node의 left, right child
vector<int> isVisited; // root를 구하기 위한 배열 (자식 노드 번호에 해당하는 값++)
vector<vector<int>> grid; // 각 노드에 해당하는 행과 열 정보 저장
void input(){
cin >> n;
graph.assign(n + 1, {});
isVisited.assign(n + 1, 0);
for(int i = 0; i < n; i++){
int n, l, r;
cin >> n >> l >> r;
graph[n] = {l, r};
// 들어오는 간선 체크
if(l != -1) isVisited[l]++;
if(r != -1) isVisited[r]++;
}
}
// 중위 순회를 통해서 각 노드의 열과 행의 위치를 찾고, grid 배열에 입력
void inOrder(int cur, int level){
if(cur == -1) return;
inOrder(graph[cur].left, level + 1);
if(grid.size() <= level) grid.resize(level + 1);
grid[level].emplace_back(col++);
inOrder(graph[cur].right, level + 1);
}
// 각 레벨마다 열을 정렬해서 너비를 구하고, 최대 너비와 레벨을 구한다.
void getMaxWidth(){
int width = 0;
for(int i = 1; i < grid.size(); i++){
sort(grid[i].begin(), grid[i].end());
width = grid[i][grid[i].size() - 1] - grid[i][0] + 1;
if(width > result_width){
result_width = width;
result_level = i;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
input();
int root = 0;
for(int i = 1; i <= n; i++){
if(isVisited[i] == 0){
root = i;
break;
}
}
inOrder(root, 1);
getMaxWidth();
cout << result_level << " " << result_width;
return 0;
}
728x90