🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map((it) => it.split(' ').map(Number));
const [n] = inputs[0];
const tree = Array.from({ length: n + 1 }, () => []);
let visited = Array(n + 1).fill(0);
for (let i = 1; i < inputs.length; i++) {
let front = 0;
const startNode = inputs[i][front++];
while (inputs[i][front] !== -1) {
const endNode = inputs[i][front++];
const cost = inputs[i][front++];
tree[startNode].push([endNode, cost]);
}
}
const farthestNode = [0, 0];
const dfs = (node, cost) => {
visited[node] = true;
if (cost > farthestNode[1]) {
farthestNode[0] = node;
farthestNode[1] = cost;
}
for (let i = 0; i < tree[node].length; i++) {
const [nextNode, nextCost] = tree[node][i];
if (!visited[nextNode]) dfs(nextNode, nextCost + cost);
}
};
dfs(1, 0);
visited = Array(n + 1).fill(0);
dfs(farthestNode[0], 0);
console.log(farthestNode[1]);🟢 풀이
⏰ 소요한 시간 : -
처음에는 인접 행렬형태로 풀이했는데 메모리 초과를 받았다.
질문게시판에서 아래와 같은 글을 봤다.
노드를 구슬, 노드 사이의 거리를 구슬을 잇는 실의 길이라고 생각한다.
이 때 아무구슬이나 잡고 바닥으로 쭉 늘어뜨리면 그 구슬과 가장 멀리 떨어져 있는 구슬이 나온다 이 때 그 구슬을 한번 잡고 다시 쭉 늘어뜨리면 연결된 구슬들의 최장거리가 나온다는 것이다.
진짜 천재같음
즉 아무 노드에서 탐색을 해서 가장 먼 노드를 찾고, 그 모드로 다시 탐색을 해서 가장 먼 노드를 찾으면 된다.
나는 당연히 한 노드에서 안으로 들어가고 들어가고 들어가서 DFS로 풀이해야된다고 생각했는데 BFS로도 풀어지더라.. 심지어 BFS가 더 효율적임
어찌됐든 DFS로 풀이를 해보자면 먼저 트리랑 연결된 정보를 인접 리스트 형태로 파싱해서 tree 배열에 저장한다. 인접 행렬이 아닌 인접 리스트로 저장하면 필요한 노드만 탐색할 수 있다.
그리고 가장 멀리 떨어져 있는 노드를 저장할 farthestNode 배열도 만들어 줬다. 0번 인덱스에는 노드의 번호, 1번 인덱스에는 코스트를 저장한다.
dfs 함수는 현재 탐색중인 노드와 지금까지의 누적 비용을 매개변수로 받는다. 함수 내부에서는 현재 노드를 방문처리 해주고, 만약 현재 누적 코스트가 저장해놨던 farthestNode의 cost값보다 크다면 farthestNode를 갱신시켜준다.
그 후 현재 탐색중인 노드와 연결된 노드를 순회하면서 미방문이면 재귀호출을 수행한다.
다시 문제의 요점으로 돌아가서 아무 노드나 잡고 dfs를 수행시켜주면 되니까 1번 노드로 dfs함수를 호출, 그 후 방문배열을 초기화 한 뒤 farthestNode에 저장된 노드로 dfs를 순회하면 정답이 나온다.
🔵 Ref
