[백준] 22868_산책 (Javascript)

문제

BOJ22868_산책

코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const [S, E] = input[M + 1].split(' ').map(Number);
const roads = input.splice(1, M).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: N + 1 }, () => new Array());
roads.forEach(([s, e]) => {
    graph[s].push(e);
    graph[e].push(s);
});

// 작은 수부터 방문해주기 위해 오름차순으로 정렬
graph.forEach((_, i) => {
    graph[i].sort((a, b) => a - b);
});

// visited[n][0] : n번 정점의 방문 여부
// visited[n][1] : n번 정점까지의 경로
const visited = Array.from({ length: N + 1 }, () => [false, []]);

function bfs(start, end) {
    const queue = [start];
    let front = 0;
    while (queue.length > front) {
        const v = queue[front++];
        if (v === end) break;
        graph[v].forEach((e) => {
            if (!visited[e][0]) {
                visited[e][0] = true;
                visited[e][1] = [...visited[v][1], e];
                queue.push(e);
            }
        });
    }
}

visited[S][0] = true;
visited[S][1] = [S];
bfs(S, E);

// E까지 온 경로에 포함되지 않았다면 방문 해제해주고 경로 초기화
for (let i = 1; i <= N; i++) {
    if (!visited[E][1].includes(i)) {
        visited[i][0] = false;
        visited[i][1] = [];
    }
}

visited[S][0] = false; // 시작노드로 가야하니 시작 노드도 방문 해제
visited[S][1] = [];
bfs(E, S);

console.log(visited[S][1].length - 1);

코드 설명

예를 들어 아래와 같이 입력이 들어왔다고 가정해보자

9 10
1 2
2 3
3 6
6 9
9 8
8 7
7 4
4 1
1 5
5 9
1 9

위 입력은 아래와 같은 그래프 형태를 띌 것이다.

첫 번째 BFS를 수행하고 나면 visited[E][1] 에는 정점 E 까지의 최단 경로가 저장된다.

다시 S까지 갈 때는 이미 왔던 경로는 거쳐갈 수 없으니 visited[E][1]에 있는 경로를 제외한 나머지 정점은 다시 방문할 수 있도록 초기화 해주었다. 또한 S정점에 다시 방문을 해주어야 하기 때문에 예외적으로 S정점은 방문을 해제해주었다.

두 번째 BFS를 수행하고 나면 visited[S][1] 에는 S->E->S 까지의 경로가 저장된다.

답으로는 움직인 횟수를 출력해야 하니 visited[S][1].length-1을 해준다.