[BOJ#5567] 결혼식 (Python, NodeJS)

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

1 초

128 MB

20430

9174

7475

44.656%

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

---

 

제출 코드 (Python)

def dfs(frd, vis, cur, depth):
    if depth == 2:
        return
    
    for i in frd[cur]:
        if not vis[i]:
            vis[i] = True
        dfs(frd, vis, i, depth+1)

n = int(input())
m = int(input())
friends = [map(int, input().split()) for _ in range(m)]

frd = [[] for _ in range(n+1)]
vis = [False] * (n+1)
vis[1] = True

for a, b in friends:
    frd[a].append(b)
    frd[b].append(a)
    
dfs(frd, vis, 1, 0)
print(len([x for x in vis if x]) -1)

제출 코드 (NodeJS)

function dfs(friends, visited, cur, depth) {
  if (depth === 2) {
    return
  }

  for (let i of friends[cur]) {
    if (!visited[i]) {
      visited[i] = true
    }
    dfs(friends, visited, i, depth+1)
  }
}

const fs = require('fs')
// const input = fs.readFileSync('input.txt').toString().trim().split('\n')
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')

const n = parseInt(input[0])
const m = parseInt(input[1])

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

let friends = Array.from({ length: n + 1 }, () => []);
for (let i = 2; i < 2+m; i++) {
  let [a, b] = input[i].trim().split(' ').map(Number)
  if (!friends[a]) friends[a] = [];
  if (!friends[b]) friends[b] = [];
  friends[a].push(b)
  friends[b].push(a)
}

dfs(friends, visited, 1, 0)
// console.log(friends)
// console.log(visited)
console.log(visited.filter(x=>x).length-1)

 

타입에러가 많이났는데, friends 배열을 만들 때, 그냥 [] 로 빈 배열을 만들면 맨 앞 인덱스에 <1 empty item> 이라고 뜨면서 TypeError 가 나는 것 같다. 그렇기 때문에 Array.from로 배열을 불러와서 n+1개 만큼 빈 배열을 만들어 주는 것이 정답같다.

// 1. 반복가능한 객체를 배열로 전환
// 문자열을 배열로 변환
const str = 'Hello';
const chars = Array.from(str);
console.log(chars); // ["H", "e", "l", "l", "o"]

// Set을 배열로 변환
const set = new Set([1, 2, 3]);
const arr = Array.from(set);
console.log(arr); // [1, 2, 3]

// Map의 키를 배열로 변환
const map = new Map([[1, 'one'], [2, 'two']]);
const keys = Array.from(map.keys());
console.log(keys); // [1, 2]

// 2. 유사 배열 객체를 배열로 전환
// arguments 객체를 배열로 변환
function foo() {
  return Array.from(arguments);
}
console.log(foo(1, 2, 3)); // [1, 2, 3]

// NodeList를 배열로 변환
const nodeList = document.querySelectorAll('p');
const nodesArray = Array.from(nodeList);


// 3.매핑 함수를 활용한 배열생성 예시
// 각 요소를 제곱하여 배열 생성
const nums = [1, 2, 3, 4, 5];
const squared = Array.from(nums, x => x * x);
console.log(squared); // [1, 4, 9, 16, 25]