백준 5214 JS 풀이 (메모리초과 ⇒ 성공)

구하는 값

여러개의 노드가 연결된 하이퍼 튜브(이것도 그냥 여러개 연결된 노드로 보자)를 이용해서 1번 노드에서 마지막 노드까지 가는 ‘최단거리’

핵심 아이디어

최단 거리이고 각 간선의 길이가 같으므로 BFS를 이용

BFS를 이용하기위해 입력받은 번호로 연결된 노드들을 이어줘야함

노드에는 하이퍼 튜브의 idx가 하이퍼 튜브에는 노드 idx가 들어갈거임

그리고 나머지는 BFS와 동일

구현방법

Set 자료구조를 통해서 방문처리를 할 수 있다.

기존에 visited 배열로 해결하던 부분을 Set으로 만들고 방문시 add해주고 방문 판단시 set.has(next)로 판단해주면 중복 방문을 없얼 수 있고 메모리 측면에서 효율적이다

코드

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

class Queue {
    q = [];
    h = 0;
    t = 0;

    enque(v) {
        this.q[this.t++] = v;
    }
    deque() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    size() {
        return this.t - this.h;
    }
}

const [n, k, m] = input[0].split(" ").map(Number);

const graph = Array.from({ length: n + m + 1 }, () => []); // 노드 + 튜브
for (let i = 1; i <= m; i++) {
    const arr = input[i].split(" ").map(Number);

    for (const x of arr) {
        graph[x].push(n + i); // 노드에 하이퍼 idx 추가
        graph[n + i].push(x); // 하이퍼에 노드 idx 추가
    }
}
// console.log(graph);
const visited = new Set();
let find = false;
function bfs(str, dep) {
    const queue = new Queue();
    queue.enque([str, dep]);
    visited.add(str);

    while (queue.size()) {
        const [cur, d] = queue.deque();
        if (cur === n) {
            console.log(parseInt(d / 2) + 1);
            find = true;
            break;
        }

        for (const next of graph[cur]) {
            if (!visited.has(next)) {
                queue.enque([next, d + 1]);
                visited.add(next);
            }
        }
    }
}

bfs(1, 1);

if (!find) console.log(-1);