코테 및 알고리즘

백준 js 2644번

Jay_Jung 2024. 7. 8. 11:54

<문제>

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

 

 

 

<문제 핵심>

1. 결론부터 말하면 bfs를 활용하는 가계도 문제였다. 처음 문제를 풀때 dfs로 접근하여 문제를 풀었는데 결국 정답을 맞추지 못하였고 구글링을 해보니 주어진 시작 노드에서 목표 노드까지 가기 위해 몇 번의 단계(또는 1촌 관계)를 거쳐야 하는지를 계산하는 문제였다.(입력의 예시로 7번 노드에서 3번 노드)

✅ 인접 노드를 방문했으면 재 방문을 안해야한다.

✅ 그래프 구조를 노트에 그렸지만 잘못 그린것을 알 수 있었고 올바른 그림은 다음과 같다.

 

<그래프 구조>

입력 값을 토대로 구성할 수 있다. 7번 노드와 3번노드의 관계가 몇 촌이지를 맞춰야하는 문제

 

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

1. 입력값을 받은 다음 인접리스트의 형태의 그래프, 방문처리를 하기 위한 배열을 생성한다. 그리고 data의 길이만큼 그래프의 값을 채운다. 여기서 x는 7번 노드, y는 3번 노드를 의미한다.

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

const n = Number(input.shift());
const [x, y] = input
  .shift()
  .split(" ")
  .map((value) => +value);
const m = Number(input.shift());

const data = input.map((item) => item.split(" ").map((v) => +v));
const graph = Array.from({ length: n + 1 }).map(() => []);
const visited = Array.from({ length: n + 1 }).map(() => false);

// 1촌 관계를 그래프로 정리
for (let i = 0; i < data.length; i++) {
  const [x, y] = data[i];
  graph[x].push(y);
  graph[y].push(x);
}

// 사람수가 1이면 촌수 계산이 불가능하기에 -1 출력
if (n === 1) {
  console.log(-1);
}

 

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

✅ qx가 처음엔 7번 노드일 것이고 7번 노드의 인접노드인 2번 노드가 neqrQx에 해당한다. 7번 노드는 방문 되있지 않으므로 visited[qx] = true를 통해 방문 처리해준다. 이후 queue에 [2,1] 형태로 삽입되며 마찬가지로 다시 2번 노드의 인접노드인 [1, 7, 8, 9] 노드를 확인한다. 앞에서 7은 이미 방문처리를 해주었기 때문에 7을 제외한 1번, 8번, 9번 노드가 큐에 삽입되며 각각 count는 +1이 된채로 같이 삽입된다. (Ex. queue = [[1, 2], [8, 2], [9, 2]] )

 

해당 과정을 쭉 하다보면 결국 3번 노드를 찾게되고 그때의 count를 반환하면 된다. (3이 나올 것)

const BFS = (start) => {
  const queue = [[start, 0]];

  while (queue.length) {
    let [qx, count] = queue.shift();
    let nearQx = graph[qx]; // 1촌 관계 그래프 가져오기
    if (visited[qx]) continue; // 방문체크
    if (qx === y) return count;
    visited[qx] = true;

    // 1촌 관계 반복문으로 순회
    for (let i = 0; i < nearQx.length; i++) {
      let value = nearQx[i];
      if (visited[value]) continue; // 방문체크
      if (value === y) return count + 1; // y값과 일치하면 +1 해서 출력
      queue.push([value, count + 1]);
    }
  }
  return -1;
};

console.log(BFS(x));

 

<전체 코드>

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

const n = Number(input.shift());
const [x, y] = input
  .shift()
  .split(" ")
  .map((value) => +value);
const m = Number(input.shift());

const data = input.map((item) => item.split(" ").map((v) => +v));
const graph = Array.from({ length: n + 1 }).map(() => []);
const visited = Array.from({ length: n + 1 }).map(() => false);

// 1촌 관계를 그래프로 정리
for (let i = 0; i < data.length; i++) {
  const [x, y] = data[i];
  graph[x].push(y);
  graph[y].push(x);
}

// 사람수가 1이면 촌수 계산이 불가능하기에 -1 출력
if (n === 1) {
  console.log(-1);
}

const BFS = (start) => {
  const queue = [[start, 0]];

  while (queue.length) {
    let [qx, count] = queue.shift();
    let nearQx = graph[qx]; // 1촌 관계 그래프 가져오기
    if (visited[qx]) continue; // 방문체크
    if (qx === y) return count;
    visited[qx] = true;

    // 1촌 관계 반복문으로 순회
    for (let i = 0; i < nearQx.length; i++) {
      let value = nearQx[i];
      if (visited[value]) continue; // 방문체크
      if (value === y) return count + 1; // y값과 일치하면 +1 해서 출력
      queue.push([value, count + 1]);
    }
  }
  return -1;
};

console.log(BFS(x));