백준) 5567 - 결혼식 JS

📌 문제 링크

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

 

---

📌 문제 탐색하기

• 자신의 결혼식에 자신의 친구와 친구의 친구까지 초대한다면 초대할 사람의 수는 몇명일지 구하려라
• 자기 자신은 1번이다.

시간복잡도

• O(N + M)

알고리즘 선택

• BFS

---

📌 코드 설계하기

1. 문제의 `input`을 개행으로 분리하여 `n`, `m`, `arr`로 값을 가져옵니다.
2. `n`과 `m`을 숫자로 변환합니다
3. `arr`은 띄어쓰기로 분리하여 숫자로 변환해서 `relationships`를 초기화해줍니다.
4. `graph` 배열을 만듭니다.
5. 양방향 관계를 설정합니다.
6. `visited`배열을 `n+1`크기로 만들고 `false`로 초기화합니다.
7. 자기 자신은 방문 처리 합니다.
8. 초대할 사람 수를 셀 `count`변수를 초기화합니다.
9. `queue`를 `[[1, 0]]`으로 초기화합니다 (시작점과 depth)
10. `queueIndex`를 0으로 초기화하여 `queue` 순회를 시작합니다
11. `queue`를 순회하면서
    • 현재 위치와 깊이를 가져옵니다
    • 깊이가 2 이상이면 건너뜁니다 (친구의 친구까지만)
    • 현재 노드의 친구들을 확인합니다:
      • 방문하지 않은 친구라면:
        • 방문 처리를 합니다
        • 큐에 [친구번호, 현재깊이+1]을 추가합니다
        • 초대할 사람 수 `count`를 증가시킵니다
12. 최종적으로 `count`를 반환합니다

---

📌 정답 코드

//https://www.acmicpc.net/problem/5567
export {};

const fs = require('fs');
const filePath =
  process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input2.txt';
const [n, m, ...input] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n');

const [N, M] = [n, m].map(Number);
const relationships = input.map((x: string) => x.split(' ').map(Number));
const graph: number[][] = Array.from({ length: N + 1 }, () => []);

for (const [a, b] of relationships) {
  graph[a].push(b);
  graph[b].push(a);
}

const visited = new Array(n + 1).fill(false);
visited[1] = true;

let count = 0;
const queue: [number, number][] = [[1, 0]];
let queueIndex = 0;

while (queueIndex < queue.length) {
  const [current, depth] = queue[queueIndex++];

  if (depth >= 2) continue;

  for (const friend of graph[current]) {
    if (!visited[friend]) {
      visited[friend] = true;
      queue.push([friend, depth + 1]);
      count++;
    }
  }
}

console.log(count);