16947 지하철 2호선 (자바스크립트)

문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

 

========

문제 분석 

 순환 되는 사이클과 지선을 찾으면 되는 문제였다.

순환 되는 사이클을 찾는 것은 DFS를 통해 찾으면 쉽게 찾을 수 있다. 

지선이 되는 것은 우선 연결된 선이 딱 1개인 정점들부터 찾으면 된다. 

연결된 선이 1개라는 것은 사이클에 해당되지 않는다는 정점이라는 의미이기 때문이다.

그러한 정점을 찾았다면 해당 점에서 출발하여 순환선까지의 최소 거리를 구하면 된다. 

최소 거리를 구하면 되므로 이때는 BFS로 탐색을 하면 된다.

오답 노트

1. 위에 적은 로직대로 풀어서 정답은 맞혔지만 순환 사이클을 찾는 것에서 한 점에서 출발하여 사이클을 찾을 수 있었는데 중복 탐색이 되는 코드를 만들어버림. 시간 초과는 나오지 않았지만 나중에 다시 짜봐도 될듯

2. 정답 출력할 때 배열 그대로 출력해서 계속 틀리게 나옴. 배열을 출력할땐 문제 출력 유형에 맞춰 array.join(' ')을 해보자

정답 코드

const main = (input) => {
    const n = +input[0];
    const gr = Array.from({ length: n + 1 }, () => []);
    const cnt = Array.from({ length: n + 1 }).fill(0);
    for (let i = 1; i < input.length; i++) {
        const [s, e] = input[i].split(' ').map((v) => +v);
        gr[s].push(e);
        gr[e].push(s);
        cnt[s] += 1;
        cnt[e] += 1;
    }

    const distance = Array.from({ length: n + 1 }).fill(1_000_000_000);
    const startPoint = [];
    const cyclePointTemp = [];
    for (let i = 0; i < cnt.length; i++) {
        if (cnt[i] === 1) {
            startPoint.push(i);
        } else {
            cyclePointTemp.push(i);
        }
    }

    if (startPoint.length === 0) { 	// 연결선이 1개인 정점이 없다는 것은 지선이 없다는 의미
        console.log(Array.from({ length: n }).fill(0).join(' '));
        return;
    }
    const cyclePoint = cyclePointTemp.filter((node) => {
        const visited = Array.from({ length: n + 1 }).fill(-1);
        visited[node] = 0;
        let answer = false;

        const dfs = (cur) => {
            for (const next of gr[cur]) {
                if (visited[next] !== -1) {
                    if (visited[cur] - visited[next] > 1 && next === node) {
                        answer = true;
                        return;
                    }
                    continue;
                }
                visited[next] = visited[cur] + 1;
                dfs(next);
            }
        };
        dfs(node);
        if (answer) {
            distance[node] = 0;
        }
        return answer;
    });

    startPoint.forEach((start) => {
        const q = [start];
        const parent = Array.from({ length: n + 1 }).fill(-1);

        parent[start] = start;
        let endPoint;
        while (q.length) {
            const cur = q.shift();
            if (cyclePoint.includes(cur)) {
                endPoint = cur;
                break;
            }
            for (const next of gr[cur]) {
                if (parent[next] !== -1) continue;
                parent[next] = cur;
                q.push(next);
            }
        }
        while (parent[endPoint] !== endPoint) {		
            distance[parent[endPoint]] = Math.min(
                distance[endPoint] + 1,
                distance[parent[endPoint]]
            );
            endPoint = parent[endPoint];
        }
    });
    console.log(distance.slice(1).join(' '));
};

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

main(input);