백준5567 - 결혼식 (그래프) JS

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

 

해당 문제는 '친구 관계 리스트'를 통해 '친구의 친구까지'의 인원들을 구하는 문제다.

그렇기에 관계 리스트를 '각 노드마다 연결된 그래프'로 구현하고,

'친구의 친구까지' 이므로 '1과 연결된 노드들', '1과 연결된 노드들과 연결된 노드들'을 정답으로 제출하면 된다.

 

소스 코드는 다음과 같다.

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

// 이때 N은 총 노드 수 / _ 은 리스트의 길이 / rest 는 관계를 나타내는 데이터
const [N,_,...rest] = input

function solution(data) {
  // 그래프 구현
  const table = Array.from({length : +N+1}, ()=> [])
  data.forEach((el)=> {
    const [to,from] = el.split(' ').map(Number)
    table[to].push(from)
    table[from].push(to)
  })

  // 노드를 중복으로 세지 않기 위한 Set()
  const result = new Set()

  // 노드 1과 연결된 노드들 추가
  table[1].forEach((friend)=> {
    result.add(friend)
    // 연결된 노드들과 연결된 노드들 추가
    table[friend].forEach((friendOfFriend)=> {
      result.add(friendOfFriend)
    })
  })
  
  // 마지막에 제외해야 할 1을 빼서 반환
  console.log(result.size !== 0 ? result.size - 1 : 0)
}

solution(rest)