[백준] 트리 #11725

설명

dfs, bfs 두 가지 모두 풀 수 있는 문제
dfs는 보통 stack 또는 재귀를 활용해 풀고,
bfs는 queue를 사용해서 푸는 것을 복습했다.

Node.js 풀이(dfs)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input[0]);
const data = input.slice(1).map((v) => v.split(' ').map(Number));

const solution = (N, data) => {
  const arr = Array.from(Array(N + 1), () => new Array());
  data.forEach(([v1, v2]) => {
    arr[v1].push(v2);
    arr[v2].push(v1);
  });
  const answer = [];
  const check = new Array(N + 1).fill(false);
  const dfs = (v) => {
    check[v] = true;
    for (const node of arr[v]) {
      if (!check[node]) {
        check[node] = true;
        answer[node - 1] = v;
        dfs(node);
      }
    }
  };
  dfs(1);
  return answer.slice(1).join('\n');
};

console.log(solution(N, data));

Node.js 풀이(bfs)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const data = input.slice(1).map((v) => v.split(' ').map(Number));

class Node {
  prev = null;
  next = null;
  constructor(value) {
    this.value = value;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) this.head = newNode;
    if (this.tail) {
      this.tail.next = newNode;
      newNode.prev = this.tail;
    }
    this.tail = newNode;
    this.length += 1;
  }
  pop() {
    if (this.length === 0) return -1;
    const value = this.head.value;
    this.head = this.head.next;
    this.length -= 1;
    return value;
  }
  front() {
    return this.length ? this.head.value : -1;
  }
  *[Symbol.iterator]() {
    let cur = this.head;
    while (cur) {
      yield cur.value;
      cur = cur.next;
    }
  }
}

const solution = (N, data) => {
  const arr = Array.from(Array(N + 1), () => new Array());
  data.forEach(([v1, v2]) => {
    arr[v1].push(v2);
    arr[v2].push(v1);
  });
  const answer = [];
  const check = new Array(N + 1).fill(false);
  const queue = new Queue();
  queue.push(1);
  while (queue.length) {
    const v = queue.pop();
    check[v] = true;
    for (const node of arr[v]) {
      if (!check[node]) {
        answer[node - 2] = v;
        queue.push(node);
      }
    }
  }
  return answer.join('\n');
};

console.log(solution(N, data));

C++ 풀이 (dfs)

#include <bits/stdc++.h>
using namespace std;

#define MAX 100001

int N; 
int arr[MAX]; 
bool visited[MAX]; 
vector<int> v[MAX];

void dfs(int k) { 
    visited[k]=true; 
    for(int i=0;i<v[k].size();i++) { 
        int next = v[k][i]; 
        if(!visited[next]) { 
            arr[next]=k; 
            dfs(next); 
        } 
    }
} 

int main() { 
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N; 
    for(int i=0;i<N-1;i++) { 
        int x,y; 
        cin >> x >> y; 
        v[x].push_back(y); 
        v[y].push_back(x); 
    } 
    dfs(1); 
    for(int i=2;i<=N;i++) cout << arr[i] << "\n"; 
}