5214 환승 (자바스크립트)

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

=====

문제 풀이

노드들끼리의 연결이 s ,e 로 주는 것이 아닌 여러 개의 연결 상황들을 주기 때문에 기존 탐색 방식처럼 한 지점에서 갈 수 있는 지점들을 기록한 뒤에 현재 노드로부터 다음 노드로 가는 방식은 연결 상황이 최대 1,000*1,000*1,000 이므로 시간 초과와 메모리 초과가 발생한다. 

그래서 생각해낸 방법은 각 노드에 대해 visited를 선언한 뒤 INFINITY를 할당하고 1번을 포함하고 있는 하이퍼튜브부터 visited[노드] 에 1을 기록해둔다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, k, m] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) => s.split(' ').map(Number));

const visited = Array.from({ length: n + 1 }, () => Infinity);
const willVisiteLines = [];

for (let i = 0; i < m; i++) {
    const curArr = arr[i];
    if (curArr.includes(1)) {
        for (const v of curArr) {
            visited[v] = 2;
        }
    } else {
        willVisiteLines.push(i);
    }
}

if (willVisiteLines.length === m) {
    console.log(-1);
    process.exit(0);
}

visited[1] = 1;

 그 다음 1번과 관련되어 있던 노드와 연결 된 다른 하이퍼튜브를 방문해서 visited[노드]+1 을 기록해준다. 

아직 방문 처리를 해보지 않은 하이퍼튜브라면 다시 한 번 처리해줘야 하므로 큐에 넣어준 뒤 위의 로직을 다시 실행한다. 

만약 다시 처리 해줘야 하는 경우의 수들이 이 전의 갯수들과 같다면 더이상 방문을 못하는 거니 실패인 것이다.

while (willVisiteLines.length) {
    const reTry = [];
    const previousLength = willVisiteLines.length;

    while (willVisiteLines.length) {
        const curLine = willVisiteLines.pop();

        const isVisit = arr[curLine].some((v) => visited[v] !== Infinity);

        if (isVisit) {
            let smallest = Infinity;
            for (const v of arr[curLine]) {
                smallest = Math.min(smallest, visited[v]);
            }
            for (const v of arr[curLine]) {
                if (visited[v] === smallest) continue;

                visited[v] = smallest + 1;
            }
        } else {
            reTry.push(curLine);
        }
    }

    if (reTry.length === previousLength) {
        console.log(-1);
        process.exit(0);
    }
    willVisiteLines.push(...reTry);
}

 

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, k, m] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) => s.split(' ').map(Number));

const visited = Array.from({ length: n + 1 }, () => Infinity);
const willVisiteLines = [];

for (let i = 0; i < m; i++) {
    const curArr = arr[i];
    if (curArr.includes(1)) {
        for (const v of curArr) {
            visited[v] = 2;
        }
    } else {
        willVisiteLines.push(i);
    }
}

if (willVisiteLines.length === m) {
    console.log(-1);
    process.exit(0);
}

visited[1] = 1;

while (willVisiteLines.length) {
    const reTry = [];
    const previousLength = willVisiteLines.length;

    while (willVisiteLines.length) {
        const curLine = willVisiteLines.pop();

        const isVisit = arr[curLine].some((v) => visited[v] !== Infinity);

        if (isVisit) {
            let smallest = Infinity;
            for (const v of arr[curLine]) {
                smallest = Math.min(smallest, visited[v]);
            }
            for (const v of arr[curLine]) {
                if (visited[v] === smallest) continue;

                visited[v] = smallest + 1;
            }
        } else {
            reTry.push(curLine);
        }
    }

    if (reTry.length === previousLength) {
        console.log(-1);
        process.exit(0);
    }
    willVisiteLines.push(...reTry);
}

if (visited[n] === Infinity) {
    console.log(-1);
} else {
    console.log(visited[n]);
}