백준 js - 18126번

 

<문제>

 

https://www.acmicpc.net/problem/18126

 

 

 

<문제 핵심>

1. dfs를 활용하는 문제였고 1번 노드부터 시작해서 dfs를 호출하게 되는데 호출하면서 연결된 인접노드 까지 탐색하게 되고 탐색하는 과정에서 인접노드 까지의 거리를 구한다.

 

2. 입력을 보면 두번째 줄 부터 3번 째 항목에 간선의 길이가 나와있다. 즉 그래프를 생성 후 데이터를 넣어줄 때 간선의 길이까지 같이 넣어줘야 하는 문제였다.

<입력 데이터>
1  2  3
2  3  2
2  4  4

for (let i = 0; i < n - 1; i++) {
  const [a, b, c] = input[i].split(" ").map(Number);
  graph[a].push([b, c]); //c는 간선의 길이를 의미한다.
  graph[b].push([a, c]); 
}

 

3. 그래프의 형태는 입력값을 보고 그려봤다.

 

<문제 풀이과정 및 순서도>

1.  graph, distacne, visited 배열을 생성 및 초기화 해주고 반복문을 통해서 graph에 데이터를 삽입해준다.

✅ 양방향 그래프 이기 때문에 graph[a].push([b, c]), graph[b].push([a, c]) 처럼 삽입

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +input.shift(); //4

const graph = Array.from({ length: n + 1 }, () => []);
const distance = Array.from({ length: n + 1 }, () => 0);
const visited = Array.from({ length: n + 1 }, () => false);

for (let i = 0; i < n - 1; i++) {
  const [a, b, c] = input[i].split(" ").map(Number);
  graph[a].push([b, c]); //c는 간선의 길이를 의미한다.
  graph[b].push([a, c]);
}

 

2. dfs함수 로직을 구현한다.

✅ 방문처리한 노드를 기준으로 그래프에 접근하게 되면 인접노드와 인접노드 까지의 거리를 알 수 있다.

✅ 인접노드 까지의 거리를 구해준다음 인접노드를 다시 dfs함수로 호출하여 인접노드의 인접노드까지 거리를 구한다. 

-> 이 과정이 반복되면 이제 모든 노드를 방문한 순간이 올텐데 그때의 distance배열의 최대값을 구해준다

const dfs = (node) => {
  visited[node] = true;
  for (let [nextNode, dist] of graph[node]) {
    if (!visited[nextNode]) {
      distance[nextNode] = distance[node] + dist;
      dfs(nextNode);
    }
  }
};

dfs(1);

console.log(Math.max(...distance));

 

<전체 코드>

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +input.shift(); //4

const graph = Array.from({ length: n + 1 }, () => []);
const distance = Array.from({ length: n + 1 }, () => 0);
const visited = Array.from({ length: n + 1 }, () => false);

for (let i = 0; i < n - 1; i++) {
  const [a, b, c] = input[i].split(" ").map(Number);
  graph[a].push([b, c]); //c는 간선의 길이를 의미한다.
  graph[b].push([a, c]);
}

const dfs = (node) => {
  visited[node] = true;
  for (let [nextNode, dist] of graph[node]) {
    if (!visited[nextNode]) {
      distance[nextNode] = distance[node] + dist;
      dfs(nextNode);
    }
  }
};

dfs(1);

console.log(Math.max(...distance));