[JavaScript] 백준 11725 : 트리의 부모 찾기

class : 4
level : silver 2
문제 링크 : 트리의 부모 찾기

11725번: 트리의 부모 찾기

My Solution

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

const N = Number(input.shift());

function solution(arr, n){
    let temp = [];
    let visited = new Array(n).fill(false);
    let answer = new Array(n).fill('');
    let queue = [0];

    for(let i = 0; i < n; i++)
        temp.push([]);
    
    arr.forEach((value)=>{
        const [a,b] = value.split(' ').map(Number);
        temp[a-1].push(b-1);
        temp[b-1].push(a-1);
    });

    while(queue.length>0){
        const index = queue.shift();
        visited[index] = true;
        temp[index].forEach((value)=>{
            if(!visited[value]){
                queue.push(value);
                answer[value] = `${index+1}`;
            }
        })
    }
    return answer.join('\n').trim();
}

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

풀이방법
위 문제는 그래프 이론 문제이다.
가장 루트 노드를 1로 잡은 다음 모든 Node의 개수 N과 모든 관계 Edge를 string으로 주어졌다.
일단 N과 Edge들의 관계를 분리하였고 두 개를 파라미터로 갖는 solution 함수를 만들었다.

solution함수에서 관계를 위한 2차원 matrix인 temp와 Node의 방문 여부를 위한 visited Array와 각 원소들의 부모 원소들을 적기 위한 answer Array, 마지막으로 bfs를 위한 queue를 초기화한다. queue에는 최상단 Node인 0을 넣고 초기화한다.

Node들의 관계 string들을 원소로 가지는 Array인 arr에서 각각의 Node가 연결된 Node들의 Array를 가지도록 반복문을 실행한다.

queue가 비어있지 않을 때까지 아래의 행위를 반복한다.

1. queue의 원소 하나를 Dequeue하여 index라 명명한다.

2. visited에서 index의 값을 true로 바꾼다.

3. temp[index]에서 방문하지 않은 Node들을 queue에 Enqueue하고 그 값들을 인덱스로 가지는 answer값에는 index+1을 가지게 한다.

반복문이 종료되었을 경우 answer에는 0번 인덱스를 제외한 모든 인덱스에 부모 노드의 값이 생성된다.

그리하여 answer를 join과 trim이라는 메서드를 이용하여 string 값을 반환한다.

느낀점
풀이방식을 최대한 HackerRank와 프로그래머스처럼 로직을 위한 함수를 따로 만들어 작성하였다.
일반적으로 개발을 할 때에도 이러한 방식으로 많이 작성하기 위해서 스타일을 바꾸었다.
남들이 최대한 편하게 볼 수 있고 나중에 고치기도 쉽게하기 위해서 더욱 노력해야겠다.