문제
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예시
| n | vertex | return |
|---|---|---|
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
풀이
전형적인 그래프 문제이다. 시작노드인 1번에서 가장 멀리 떨어진 노드의 개수를 찾는 문제인데 이는 사실 DFS와 BFS 어떤 방식으로 구현하더라도 가능하다. 하지만 여기에서도 잠깐 언급한 바와 같이 본인은 JS에서 DFS가 꼭 필요한 상황이 아니라면 별로 선호하지 않는다. 따라서 BFS로 구현해보자.
먼저 주어진 vertex를 이용해서 연결된 노드들의 정보를 만들어 줄 것이다. 이는 대부분 그래프 문제에서 선행되는 작업이기도 하니 한 번 익혀두면 두고두고 쓰일 수 있다. 다음의 형태로 연결관계를 나타내보자.
[
[...연결된 노드번호], //0번째(= 노드1)
[...연결된 노드번호], //1번째(= 노드2)
[...연결된 노드번호], //2번째(= 노드3)
...
]이를 코드로 나타내면 아래와 같다.
// 노드 크기만큼의 2차원 배열을 선언하는 과정이다.
const connects = new Array(n).fill().map(_ => []);
for(const e of edge) {
// 양방향 그래프이므로 서로의 좌표에 모두 연결된 노드를 넣어준다.
// -1을 하는 이유는 배열의 index는 0부터 시작하는 반면
// 주어진 노드 번호는 1부터 시작하기 때문이다.
connects[e[0]-1].push(el[1]-1);
connects[e[1]-1].push(el[0]-1);
}연결리스트를 만들었다면 BFS를 통해 가장 멀리있는 노드의 개수를 체크할 것이다. 여기서 쓰이는 테크닉은 이전 포스트에서도 동일하게 사용한 것인데 바로 그래프의 deps를 추적할 것 이다. 기본적으로 BFS는 현재 deps에 해당하는 노드들을 먼저 다 탐색한 뒤 다음 deps로 넘어가기 때문에 현재 deps값을 추적하여 가장 멀리 있는 노드를 탐색할 수 있다. 해당 deps 값 추적은 동일하게 visited 변수를 선언하여 해당 변수에 방문의 표시로 자신의 deps 값을 넣어주는 방식으로 구현했다. 이미 위 링크된 포스트에서 설명된 바 있으므로 바로 구현된 코드를 확인하자.
const visited = [1]; // deps임과 동시에 반환값에 개수로 사용할 것이므로 바로 1로 시작하게끔 초기화
const queue = [0];
while(queue.length) {
const cur = queue.shift();
// 현재노드(cur)와 연결된 노드들을 돌아가며
for(const next of connects[cur]) {
// 연결된 노드 중 지금 차례의 노드(next)가
// 아직 방문하지 않은 상태라면
if(!visited[next]) {
// 방문처리함과 동시에 그 값을 현재 deps + 1로 삽입
visited[next] = visited[cur] + 1;
queue.push(next);
}
}
}
위의 BFS를 모두 돌고나면 visited 배열에는 각 deps가 담겨있을 것이다. 각각의 값은 노드 1번으로부터 떨어져있는 거리를 의미한다. 우리가 필요한 것은 가장 멀리 떨어진 노드이므로 먼저 해당 visited 배열에서 최댓값을 찾은 뒤, 그 최댓값이 배열에 모두 몇개 있는지를 찾아 반환해주면 될 것 이다.
const max = Math.max(...visited);
return visited.filter(el => el === max).length;전형적인 그래프 탐색 문제이기에 크게 어렵지 않다. BFS에 대한 이해가 깊다면 매우 손쉽게 해결할 수 있을 것이다. 주석을 제외한 전체 코드는 다음과 같다.
코드
function solution (n, edge) {
const connects = new Array(n).fill().map(_ => []);
for(const e of edge) {
connects[e[0]-1].push(e[1]-1);
connects[e[1]-1].push(e[0]-1);
}
const visited = [1];
const queue = [0];
while(queue.length) {
const cur = queue.shift();
for(const next of connects[cur]) {
if(!visited[next]) {
visited[next] = visited[cur] + 1;
queue.push(next);
}
}
}
const max = Math.max(...visited);
return visited.filter(el => el === max).length;
}출처
https://programmers.co.kr/learn/courses/30/lessons/49189?language=javascript
