[JS] 배달

그래프 문제입니다.

간선 별로 가중치가 다르게 설계되어있네요.

최솟값을 묻는 문제이니, 우리 많이 당해봤잖아요? 그쵸?

BFS를 써서 문제를 풀어봅시다!

---

문제 요약

N은 마을의 수, K는 배달까지 걸리는 최대 시간입니다.

1번 마을에서 출발해서 K 시간 이하로 갈 수 있는 모든 마을의 수를 return해주세요!

 

입출력 예

N	road	K	result
5	[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]	3	4
6	[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]	4	4

 

접근 방법

일단 BFS를 설계하기 위해서는 큐를 만들어줘야합니다.

이번 문제에서는 간선의 방향이 중요하지 않습니다. 만약 1번 마을에서 시작하는 길을 찾으려면

const vil1 = road.filter(v => v[0] === 1 || v[1] === 1);

이렇게 찾을 수 있겠군요!

저는 편의상 큐에 [start, end, length] 이렇게 넣어줬습니다. 이걸 생각 안해주면 마을 1에서 마을 2를 갔다가 다시 되돌아오는 루프에 빠질 수도 있습니다. 잘 조절해서 넣어줍시다!

 

또 중요한 점은 일반적인 bfs/dfs에서는 visited를 방문했냐 안했냐가 중요하기 때문에 boolean의 배열로 넣지만, 여기선 그렇게 중요하지 않을 수 있습니다. 예를 들어 이걸 보시죠!

 

그림판으로 그렸는데요... ㅠㅠㅠㅠ

일단 무조건 1번 노드에서 시작하기 때문에 무조건 3번 노드를 방문하게 됩니다.

그런데 사실 가장 빨리 갈 수 있는 방법은 4번 마을로 우회하는 방법이죠. (직행하는경우: 3, 4번 우회하는 경우: 2)

visited가 boolean이면 4번에서 3번 넘어가는 경우의 수는 무조건 걸러지게 됩니다.

따라서 초기값을 Infinity로 설정한 숫자 배열로 넣어줘야합니다.

그러면 제가 짠 코드를 같이 보시죠!

 

정답 코드(BFS)

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(val) {
        this.queue[this.rear++] = val;
    }
    
    dequeue() {
        const val = this.queue[this.front];
        delete this.queue[this.front];
        this.front++;
        return val;
    }
    
    size() {
        return this.rear - this.front;
    }
    
    isEmpty() {
        return this.rear === this.front;
    }
}

function solution(N, road, K) {
    const queue = new Queue();
    const node1 = road.filter(v => v[0] === 1 || v[1] === 1);
    node1.forEach(v => {
        if (v[2] <= K) {
            if (v[0] === 1) queue.enqueue([v[0], v[1], v[2]]);
            else queue.enqueue([v[1], v[0], v[2]]);
        }
    });
    const visited = [Infinity, 0, ...Array(N - 1).fill(Infinity)];
    
    while (!queue.isEmpty()) {
        const [start, end, length] = queue.dequeue();
        if (visited[end] >= length) visited[end] = length;
        else continue;
        const next = road.filter((v) => v[0] === end || v[1] === end);
        for (const vilage of next) {
            const nextLength = length + vilage[2];
            if (nextLength <= K){
                if (vilage[0] === end) {
                    queue.enqueue([vilage[0], vilage[1], nextLength]);
                }
                if (vilage[1] === end) {
                    queue.enqueue([vilage[1], vilage[0], nextLength]);
                }
            }
        }
    }
    return visited.filter(v => v <= K).length;
}

 

가중치가 1이 아니기 때문에 visited를 숫자로 넣어줘야한다는 팁을 얻었습니다.

간단히 주요 요소들 한번 리뷰하고 넘어가죠!

 

팁 1. visited의 초기화

const visited = [Infinity, 0, ...Array(N - 1).fill(Infinity)];

전 visited를 N + 1 개만큼 만들어줬습니다. index로 편하게 접근하고 싶었어요.

문제 제한 사항으로 0번 마을이 나올일이 없으니 전부 Infinity로 초기화 해주시고, 1번 마을만 0을 넣어주면 되겠네요. (시작점이니까요)

 

팁 2. bfs 루프

while (!queue.isEmpty()) {
        const [start, end, length] = queue.dequeue();
        // visited에 적힌 값보다 지금 루트가 길이가 작다면 갱신 크다면 다음 분기로
        if (visited[end] >= length) visited[end] = length;
        else continue;
        const next = road.filter((v) => v[0] === end || v[1] === end);
        for (const vilage of next) {
            const nextLength = length + vilage[2];
            if (nextLength <= K){
            //이 분기는 v[0]과 v[1]에 end가 있는 경우를 모두 고려했기 때문에 걸러줍니다.
                if (vilage[0] === end) {
                    queue.enqueue([vilage[0], vilage[1], nextLength]);
                }
                if (vilage[1] === end) {
                    queue.enqueue([vilage[1], vilage[0], nextLength]);
                }
            }
        }
    }

전 그냥 제 편의상 start에는 이전 노드를 end에는 이번 노드, length는 여태까지 경로의 총합을 넣어줬습니다.

그래서 이전노드를 start 위치에 두기 위한 귀찮은 분기가 생겼지만 그래도 괜찮게 푼 것 같습니다.

 

그럼 이만!