백준 1325번 (시간 초과)

QUESTION LINK

그래프 순회를 이용해 해결하는 문제입니다. 문제를 해결하기 위해 일단 주어진 값들에 대해서 그래프로 만들어주는 작업이 먼저 필요했습니다.
그래프를 그리기에 앞서 문제에 대한 파악이 먼저 필요했는데, 여기서 예를 들어 A가 B를 신뢰하는 경우는 그래프 상으로는 ‘B → A’와 같은 형태가 나온다고 볼 수 있습니다. 이를 이용해 그래프를 만들면 아래와 같은 형태의 그래프가 나오게 됩니다.

const graph = {
  1: ["3"],
  2: ["3"],
  3: ["4", "5"],
  4: ["5"],
};

이후 DFS를 통해서 해당 그래프를 순회하며 연결된 노드들이 지나갈 때마다 횟수를 1회 더해주어 총 지나간 횟수를 구하는 함수를 만들었습니다.

const dfs = (start) => {
  const queue = [start];
  // 방문할 노드를 담아두는 배열
  const visited = {};
  // 방문한 노드를 적어두는 곳
  let count = 0;
  // 총 방문한 노드 수
  let node;
  // 현재 노드 설정
  visited[start] = true;
  // 시작점의 노드는 방문한 것으로 처리

  while (queue.length) {
    node = queue.pop();
    // 배열의 가장 마지막 요소를 빼내고, 이를 확인했다는 의미로 count의 숫자를 올림
    count += 1;

    if (!graph[node]) graph[node] = [];
    // 해당 노드를 통해 접근가능한 값이 없는 경우에 대해 빈 배열로 처리함

    graph[node].forEach((nextNode) => {
      if (!visited[nextNode]) {
        // 인접 노드에 대해서도 방문하지 않았을 시 같은 방법으로 순회하도록 함
        visited[nextNode] = true;
        queue.push(nextNode);
      }
    });
  }

  return count;
};

이후 그래프의 key값들을 통해 그래프 순회를 시작합니다. 이 때 최대값과 결과 배열을 설정해두어, 최대값을 갖고 있는 값들의 배열을 구합니다.

let resultArray = [];
// 결과 배열
let curMax = 0;
// 초기 최대값 설정
const graphKeys = Object.keys(graph);

graphKeys.forEach((index) => {
  const curCount = dfs(index);
  if (curMax > curCount) return;
  // 최대값보다 작은 값이 나올 경우 취소
  if (curMax === curCount) resultArray.push(index);
  // 최대값과 일치할 경우 기존 배열에 삽입
  if (curMax < curCount) {
    // 최대값보다 클 경우 새롭게 최대값 설정 후 결과 배열을 변경
    curMax = curCount;
    resultArray = [index];
  }
});

하지만, 현재 이렇게 값을 구할 경우, 예제로 나온 부분에 대해서는 처리가 가능하나, 이후 백준을 통해서 채점을 진행할 경우 지속적으로 시간 초과가 나오는 상태입니다. 해당 부분을 처리하기 위한 작업을 추가적으로 진행해야 합니다.

GITHUB  EMAIL