[JavaScript] 백준 15591 MooTube (JS)

MooTube

📚 문제 설명

두 동영상가 얼마나 비슷한지 알 수 있는 "USADO" 라는 것이 있다.
예를 들어,
"1영상 - 2영상"이 "USADO" 3
"2영상 - 3영상"이 "USADO" 1
이라면 "1영상 - 3영상"은 Math.min(3, 1) 즉, 1이 된다.

여기서 N개의 영상에 대해 N - 1쌍의 "USADO" 가 주어졌을 때,
V번 영상과 K 유사도 이상의 관계의 있는 영상의 수를 찾아야하는 문제이다.

👨🏻‍💻 풀이 과정

이 문제에서 가장 고민을 했던 부분은 바로 "USADO"를 계산하는 부분이다.

처음에는 배열로 각각의 모든 노드의 "USADO"를 배열로 저장을 할까 고민했지만,
이 문제에서 필요한 것은 굳이 모든 "USADO"를 알 필요가 없다.

이 문제에서 내가 원하는 것은 결국 V에서 출발하여 K 안에 도착할 수 있는 노드가 몇개인지 찾는 것이다.

따라서 전체 BFS로직을 다음과 같이 구성했다.

💡 BFS

우선 BFS() 함수의 인자로는 (K, V)를 받게 만들고, 모든 연결 관계를 연결 리스트 형식의 배열로 저장해 주었다.
그리고 원하는 것은 갯수이기 때문에 cnt 변수를 이용해 갯수 세어준 후 마지막에 return.

• visited 배열로 이미 K 이상의 "USADO" 를 체크한 영상을 확인.
• Queue 에 노드들을 넣어서 반복문을 돌게 만들었다.
• 노드를 확인한 후 연결 리스트인 lists 를 이용해 "USADO"를 확인.
  • "USADO"가 K 이상이면, visited 배열 체크, cnt 값 1 증가, Queue 에 다음 노드 push()
• Queue를 모두 확인한 후, cnt 값을 리턴.

BFS 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, M] = input.shift().split(' ').map(Number);
    let lines = input.splice(0, N - 1).map(v => v.split(' ').map(Number));
    input = input.map(v => v.split(' ').map(Number));

    let lists = new Array(N + 1).fill().map(_ => []);
	// 연결 리스트 형식의 배열로 저장 [ 노드 번호, USADO ]
    for (const line of lines) {
        const [start, goal, cost] = line;
        lists[start].push([goal, cost]);
        lists[goal].push([start, cost]);
    }
	// BFS 함수
    const BFS = (limit, start) => {
        let visited = new Array(N + 1).fill(false);
      	// 시작 노드 체크
        visited[start] = true;
        let cnt = 0;
        let Queue = [start];
      	// shift() 함수를 사용하지 않기 위해 인덱스 변수 사용.
        let idx = 0;
        while (Queue.length > idx) {
            let now = Queue[idx];
          	// 연결 리스트 안을 순회.
            for (let i = 0; i < lists[now].length; i++) {
				// 연결 리스트 하나하나 확인.
                let [nextNode, nextCost] = lists[now][i];
              	// 만약 아직 가지 않은 노드라면.
                if (!visited[nextNode]) {
                  	// 해당 노드의 USADO가 K 이상인지 확인.
                    if (nextCost >= limit) {
                        visited[nextNode] = true;
                        Queue.push(nextNode);
                        cnt++;
                    }
                }
            }
          	// 큐의 다음 인덱스 확인.
            idx++;
        }
        return cnt;
    };

그리고 이제 전체 입력에 대해서 BFS 함수를 실행하는 로직만 추가하면 된다.

전체 로직

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, M] = input.shift().split(' ').map(Number);
    let lines = input.splice(0, N - 1).map(v => v.split(' ').map(Number));
    input = input.map(v => v.split(' ').map(Number));

    let lists = new Array(N + 1).fill().map(_ => []);
	// 연결 리스트 형식의 배열로 저장 [ 노드 번호, USADO ]
    for (const line of lines) {
        const [start, goal, cost] = line;
        lists[start].push([goal, cost]);
        lists[goal].push([start, cost]);
    }
	// BFS 함수
    const BFS = (limit, start) => {
        let visited = new Array(N + 1).fill(false);
      	// 시작 노드 체크
        visited[start] = true;
        let cnt = 0;
        let Queue = [start];
      	// shift() 함수를 사용하지 않기 위해 인덱스 변수 사용.
        let idx = 0;
        while (Queue.length > idx) {
            let now = Queue[idx];
          	// 연결 리스트 안을 순회.
            for (let i = 0; i < lists[now].length; i++) {
				// 연결 리스트 하나하나 확인.
                let [nextNode, nextCost] = lists[now][i];
              	// 만약 아직 가지 않은 노드라면.
                if (!visited[nextNode]) {
                  	// 해당 노드의 USADO가 K 이상인지 확인.
                    if (nextCost >= limit) {
                        visited[nextNode] = true;
                        Queue.push(nextNode);
                        cnt++;
                    }
                }
            }
          	// 큐의 다음 인덱스 확인.
            idx++;
        }
        return cnt;
    };

    const solution = (INPUT) => {
        let answer = [];
        for (const inputElement of INPUT) {
            const [LIMIT, NODE] = inputElement;
            answer.push(BFS(LIMIT, NODE));
        }
        console.log(answer.join('\n'));
    };
    solution(input);

🧐 후기

"USADO"라는 조건 때문에 어떻게 접근을 해야 하는지 고민이 많이 됐다.
그런데, 막상 생각을 해보니 결국 연결 리스트로 저장만 한다면, 일반적인 BFS로 풀면 되는 문제였다.
문제가 무엇을 원하는지 조금 더 고민을 하면서 로직을 생각해야겠다.