백준 11725: 트리의 부모 찾기 - javascript(bfs)

아직 골드 풀 때는 아닌 것 같다. 

골드 풀다가 알고리즘과 영원히 바이 할 뻔 했다. 

실버 열심히 많이 풀고 넘어가야겠다. 

이번달은 

문제 출처 

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

문제 풀이 힌트 

- 서로 연결되어 있는 노드를 tree 배열에 정리한다. 

 

- root인 1부터 밑의 자식 탐방? 을 한다. 

 

 

우리는 6과 4의 노드를 방문한 적이 없다 ! 

6과 4의 부모 노드는 1이겠구나 

 

이 과정을 반복해준다 ! 

 

그다음은 queue의 맨 앞 값이였던 6을 빼서 tree[6]을 탐방? 한다. 

자식 후보는 1과 3이다. 

근데 1은 우리가 아까 방문한 노드다 !!!

3은 방문하지 않았다. 

그러니 queue 값에 3만 넣는다. 

그리고, answer[3]에 부모 값인 6을 넣는다. 

 

이걸 반복하면 answer 배열이 나온다. 

노드 2 부터 부모 노드를 출력하라고 하니, answer.slice(2) 가 답이다 ! 

 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift(); 
const inputs = input.map(v =>v.split(' ').map(Number)); 
const tree = [...Array(N+1)].map(()=> []); 
    for(let [from, to] of inputs){
        tree[from].push(to); 
        tree[to].push(from); 
    }
const answer = []; 
function bfs(root){
    let visited = new Array(N+1).fill(false); 
    let queue = [root]; 
    visited[root] = true; 
    while(queue.length){
        let parent = queue.shift();
        let childs = tree[parent]; 
        for(let i=0; i<childs.length; i++){
            let child = childs[i]; 
            if(visited[child]) continue; 
            visited[child] = true; 
            queue.push(child); 
            answer[child] = parent; 
        }
    }
}
bfs(1);
console.log(answer.slice(2).join('\n'))

의사 코드 추가

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift(); 
const inputs = input.map(v =>v.split(' ').map(Number)); 
//연결되어있는 노드
const tree = [...Array(N+1)].map(()=> []); 
    for(let [from, to] of inputs){
        tree[from].push(to); 
        tree[to].push(from); 
    }
//해당되는 idx에 부모값을 넣을 것임. ex) answer[2] = 노드2의 부모 값    
const answer = []; 
function bfs(root){
    let visited = new Array(N+1).fill(false); 
    let queue = [root]; 
    visited[root] = true; 
    while(queue.length){
        let parent = queue.shift();
        let childs = tree[parent]; //childs는, 자식 후보들
        for(let i=0; i<childs.length; i++){
            let child = childs[i]; 
            if(visited[child]) continue; //이미 방문한 적이 있으면 자식이 아니다. 
            visited[child] = true; //방문체크 
            queue.push(child); 
            answer[child] = parent; //answer에 부모노드 값을 넣어준다. 
        }
    }
}
bfs(1);
console.log(answer.slice(2).join('\n'))