백준 알고리즘 - 1697 - 숨바꼭질 - 그래프 문제 풀이

문제 링크: https://www.acmicpc.net/problem/2667
난이도: 실버 1

 

일종의 최단 거리 찾기 문제로, BFS가 권장됩니다. -1, +1, x2 세 가지 조건으로 방문한 노드를 1차원 배열에 기록하여 완전탐색을 하다가, K 노드에 몇 번에 걸쳐 도달했는지 출력하면 됩니다. 원리는 간단하지만, 어떤 조건식을 추가하느냐에 따라 성능이 많이 달라지므로 주의가 필요합니다.

 

저는 5번째 시도에서 성공 후 코드를 리팩토링 하며 9번 더 시도하게 되었습니다.

참고할만한 포인트와 함께 몇 가지 과정을 소개해보겠습니다.

 

const visited = [];
let queue = [];
let answer = n === k ? '0' : undefined;

bfs(n, 0);

while (queue.length) {
    if (answer) break;

    const nodes = queue.shift();
    const time = nodes[0];

    for (let i = 1; i < nodes.length; i += 1) {
        if (nodes[i] === k) {
            answer = time;
            break;
        }

        if (!visited[nodes[i]]) {
            visited[nodes[i]] = time;
            bfs(nodes[i], time);
        }
    }
}

function bfs(n, time) {
    const turn = [time + 1];

    if (n < k) {
        turn.push(n + 1);
        turn.push(n * 2);
    }
    turn.push(n - 1);

    queue.push(turn);
}

console.log(answer);

 

저의 첫 번째 성공 코드입니다.

큐에는 [이동 횟수, +1, x2, -1] 네 가지 노드 번호로 이루어진 nodes 배열이 들어옵니다.

1번 인덱스부터 시작하는 반복문에 노드가 k번인지 검사하는 조건식이 있고, 방문하지 않은 노드면 이동 횟수를 증가시켜 다음 노드를 탐색하게끔 bfs 함수를 호출합니다.

별도로 분리된 bfs 함수에서는 큐에 들어갈 배열을 만들어 추가합니다.

부모 노드로 참조할 n번 노드가 k보다 커지면 +1, x2 이동은 더 이상 의미가 없으므로 해당 조건도 추가했습니다.

 

하지만 5,908ms에 달하는 시간, 100,000kb가 넘어가는 메모리 사용량을 보고 코드를 개선하기로 합니다.

 

const visited = [];
let queue = [];

if (n === k) {
    console.log(0);
    return;
} else {
    visited[n] = 0;
    bfs(n);
}

while (queue.length) {
    if (visited[k]) break;

    const nodes = queue.shift();
    const time = visited[nodes[0]] + 1;

    for (let i = 1; i < nodes.length; i += 1) {
        if (!visited[nodes[i]]) {
            visited[nodes[i]] = time;
            bfs(nodes[i]);
        }
    }
}

 

바로 다음으로 제출한 코드입니다.

주어지는 조건이 바로 n === k 임에도 bfs 함수를 호출하고 while 조건문을 태운다는 점을 개선하고, answer 변수가 크게 유의미하지 않다고 느껴 제거한 뒤, visited[k]를 참조하도록 변경했습니다.

큐 안에서 가장 먼저 visited[k]에 값이 있는지를 확인하기 때문에 nodes 배열을 순회할 때 nodes[i] === k 조건도 제거했습니다.

이전 코드에서는 bfs를 호출할 때 두 번째 매개변수로 이동 횟수를 넘겨주었는데, visited[부모 노드]를 통해 가져올 수 있으므로 정리했습니다.

 

이렇게 개선하니 시간과 코드 길이가 줄어들긴 했지만, 5,908ms -> 5,668ms로 너무 소폭 줄어들어 더 개선하기로 합니다.

 

const visited = [];
let queue = [];

if (n >= k) {
    console.log(n - k);
    return;
}

visited[n] = 0;
bfs(n);

while (queue.length) {
    if (visited[k]) break;

    const nodes = queue.shift();
    const time = visited[nodes[0]] + 1;

    for (let i = 1; i < nodes.length; i += 1) {
        if (!visited[nodes[i]]) {
            visited[nodes[i]] = time;
            bfs(nodes[i]);
        }
    }
}

function bfs(n) {
    const turn = [n];

    if (n < k) {
        turn.push(n + 1);
        turn.push(n * 2);
    }
    if (n > 0) {
        turn.push(n - 1);
    }
    queue.push(turn);
}

console.log(visited[k]);

 

n > k 인 경우 k에 도달하는 방법은 -1 뿐인데, 결론적으로 n - k로 구할 수 있는 값이기 때문에 그래프를 순회하는 것이 의미가 없었습니다.

그래서 if (n >= k) 조건식을 상단에 추가하여 n - k를 출력했고, 가독성이 좋지 않은 if (n === k) 조건식도 함께 정리했습니다.

 

그리고 0 미만으로 -1 이동을 할 필요가 없지 않냐는 @hyoguoo님의 피드백을 토대로 bfs 함수에 n > 0 조건을 추가했습니다.

 

이렇게 개선하니, 메모리 49,600kb, 시간 2,880ms로 처음보다는 상당히 개선된 성능을 보였습니다.

하지만 아직 시간이 1,000ms가 넘어가므로 더 개선할 점을 찾고 싶었습니다.

 

const visited = [];
let queue = [];

if (n >= k) {
    console.log(n - k);
    return;
}

visited[n] = 0;
queue.push(n);

while (queue.length) {
    if (visited[k]) break;

    const node = queue.shift();
    const time = visited[node] + 1;
    
    const backward = node - 1;
    const forward = node + 1;
    const teleport = node * 2;

    if (node > 0 && !visited[backward]) {
        queue.push(backward);
        visited[backward] = time;
    }
    if (node < k && !visited[forward]) {
        queue.push(forward);
        visited[forward] = time;
    }
    if (node < k && !visited[teleport]) {
        queue.push(teleport);
        visited[teleport] = time;
    }
}

console.log(visited[k]);

 

마지막으로 정리한 코드입니다.

별도 함수로 분리된 bfs를 호출할 때도 비용이 발생한다는 @hyoguoo님의 피드백이 있어 bfs에서 처리했던 과정을 while 문 안으로 옮겼습니다. 또한 큐에 nodes 배열을 넘겨 이중 반복이 발생하던 부분도 제거했습니다.

큐에서 꺼낸 (부모)node에 -1, +1, x2를 계산한 각각의 노드에 방문 기록이 없다면, queue에 추가하는 조건식으로 풀었습니다.

 

아무래도 이중 반복이 발생했던 queue 구조가 문제가 컸던 것 같습니다.

최종 성능: 메모리 100,148kb -> 28,292kb / 시간 5,908ms -> 704ms으로 처음에 비하면 상당히 개선되었습니다.

 

다른 분들의 코드 성능을 보니, 더 개선할 여지는 있을 것 같습니다만. 이 정도 코드 리팩토링도 충분한 수확이었다고 생각합니다.

한 단계 한 단계 알고리즘을 계속 풀다 보면 언젠가는 그래프 따위야 0.1초 대 성능으로 처리하는 그런 경지에 오를 수 있겠죠...?ㅎㅎ

 

 

Thanks to @hyoguoo