티스토리 뷰
title: "트리의 부모 찾기(11725)"
category: 백준[Class-4]
tags: [C++, JavaScript, 백준]
date: "2021-05-31"
문제 링크
C++
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
// 문제 풀이
void solution(){
int n;
cin >> n;
vector<int> graph[n+1];
for(int i=0; i<n; i++){
int v1, v2;
cin >> v1 >> v2;
// 연결
graph[v1].push_back(v2);
graph[v2].push_back(v1);
}
// BFS
vector<int> parent(n+1, 0);
queue<int> q;
q.push(1);
parent[1] = 1;
while(!q.empty()){
int current = q.front();
q.pop();
// 연결된 정점들
for(int v: graph[current]){
if(parent[v] == 0){
parent[v] = current;
q.push(v);
}
}
}
for(int i=2; i<=n; i++){
cout<<parent[i]<<"\n";
}
}
bool exists(const char* fileName){
FILE* fp;
if((fp = fopen(fileName, "r"))){
fclose(fp);
return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if(exists("stdin")){
freopen("stdin", "r", stdin);
solution();
fclose(stdin);
}
else{
solution();
}
return 0;
}
JavsScript
const fs = require("fs");
const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
// 문제 풀이
const n = +input[0];
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i < input.length; i++) {
const [v1, v2] = input[i].split(" ");
// 연결
graph[+v1].push(+v2);
graph[+v2].push(+v1);
}
// BFS
const parent = Array(n + 1).fill(0);
const queue = [];
parent[1] = 1;
queue.push(1);
while (queue.length > 0) {
const current = queue[0];
queue.shift(); // pop
for (const next of graph[current]) {
if (parent[next] === 0) {
parent[next] = current;
queue.push(next);
}
}
}
// 2번부터
const log = [];
for (let i = 2; i <= n; i++) {
log.push(parent[i]);
}
// print
console.log(log.join("\n"));
728x90
반응형
'Baekjoon Solutions > Class-4' 카테고리의 다른 글
[백준] 곱셈(1629) (0) | 2021.06.10 |
---|---|
[백준] RGB거리(1149) (0) | 2021.06.06 |
[백준] 가장 긴 증가하는 부분 수열(11053) (0) | 2021.05.31 |
[백준] 스티커(9465) (0) | 2021.05.29 |
[백준] 조합(2407) (0) | 2021.05.27 |
댓글