시작하며 😵

자바스크립트로 처음 그래프를 풀어보네요.
아니, 사실 그래프 자체를 6개월 만에 풀어본 거 같아요 😂
그래도 신기한 게, 결국에 답을 안 보고 충분히 풀 수 있더라구요.
알고리즘은 어떻게 푸느냐에 대한 일련의 접근이란 걸 다시금 깨달았어요.
문제가 쉬웠으려나요? (저는 이런 문제들이 오랜만이라 그런지 시간이 좀 걸렸어요!)
그럼, 시작해보겠습니다 😋

풀이과정 📃

일단 저는 이 문제를 보고 다음과 같이 생각했어요.

1. 음, 이건 노드간 가중치가 다른 게 없어서 그냥 queue로 돌리자!
2. 일단 그래프를 만들어주고!
3. 시작점은 항상 정해져 있으니, 시작점 1과 거리 0을 넣어주고(시작점이니 거리는 0), visited 처리해주자!
4. 쭉 돌리면서, visited가 안된 곳이면 큐에 넣어주고, 거리를 1씩 더해준다.
5. 큐에서 뺄 때, 현재 최대 거리와 같으면 카운트를 더해주고, 더 많으면 새로 갱신한다.

결과적으로 이를 답 처리를 하면, 깔끔하게 답이 나오네요!

사실... 원래는 distance라는 걸 하나 만들었었는데, 이걸 만드니까 메모리 초과가 떠서, 그냥 다음과 같이 배열 형태로 큐에 집어넣게 됐어요! 참고바랍니다 😵

코드

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

const initialize = n => {
    const graph = Array.from(Array(n + 1), () => []);
    const visited = Array.from(Array(n + 1), () => false)
    return [ graph, visited ]
}

const solution = (n, vertex) => {
    // 인덱스를 고려한 계산 편의성을 위해 n + 1로 설정
    const [ graph, visited ] = initialize(n);
    vertex.forEach(([a, b]) => {
        graph[a].push(b);
        graph[b].push(a);
    });

    const start = 1;

    const queue = new Queue();
    queue.enqueue([start, 0]);
    visited[start] = true;

    let maxCost = 0;
    let maxCostCount = 0;
    
    while(queue.size()) {
        const [now, cost] = queue.dequeue();
        if (maxCost < cost) {
            maxCost = cost;
            maxCostCount = 1;
        } else if (maxCost === cost) {
            maxCostCount += 1;
        }

        graph[now].forEach(next => {
            if (visited[next]) return;
            visited[next] = true;
            
            queue.enqueue([next, cost + 1]);
        })
    }
    return maxCostCount
};

마치며 🖐🏻

일단 오늘 공부 할당량은 끝났네요, 휴...

그래도 단기간에 빠르게 자료구조 및 알고리즘을 쓱 훑어보고 있어서 기분이 매우 좋아요. 역시 알고리즘과 자료구조는 재밌는 거 같아요 😊
(복잡도 줄이는 게 가장 재밌...)

그렇다면 내일도 또 풀이과정 올리러 올게요. 다들 재밌게 코딩 공부하시길!