▶ 실버 2 (트리)
문제
풀이
처음엔 queue<pair<int, int>> 를 선언하여 parent 배열이 다 채워질 때까지 노드 쌍을 queue에 다시 삽입하는 방법을 생각했다. 하지만 O(N^2) 시간복잡도로 시간 초과가 났다.
그래서 bfs, dfs 중 bfs를 이용하여 풀었다.
코드
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 100001
using namespace std;
int n;
vector<int> tree[MAX];
queue<int> q;
bool visited[MAX];
int parent[MAX];
void bfs() {
q.push(1);
while(!q.empty()) {
int start = q.front();
q.pop();
visited[start] = true;
while (!tree[start].empty()) {
int v = tree[start].back();
tree[start].pop_back();
if (!visited[v] && parent[v] == 0) {
parent[v] = start;
q.push(v);
}
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
tree[b].push_back(a);
tree[a].push_back(b);
}
bfs();
for (int i = 2; i <= n; i++) {
cout << parent[i] << "\n";
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
3584_가장 가까운 공통 조상 (0) | 2023.08.07 |
---|---|
1967_트리의 지름 (0) | 2023.08.05 |
11497_통나무 건너뛰기 (0) | 2023.03.16 |
2477_참외밭 (2) | 2023.03.12 |
1339_단어 수학 (0) | 2023.03.08 |