Problem
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다.
상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다.
이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다.
둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다.
다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다.
(1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
Comment
자신의 친구와 친구의 친구 를 초대할 수 있다는 조건만 성립하면 된다.
아래 예제 인력을 보를 보면 어떤 친구들이 이 조건에 해당 되는가?
6
5
1 2
1 3
3 4
2 3
4 5
그렇다.
[2, 3, 4] 이다 (2,3 은 상근이의 친구고 4는 상근이의 친구의 친구다.)
이 외 5와 6은 해당 되지 않는다.
시간 복잡도를 줄이기 위해서 처음에 고려한 인접 행렬 O(n^2)이 아닌, 인접 리스트 O(n+m)로 구현 했다.
최단 거리 알고리즘으로 어떤걸 채택할지 고민하다가 전체 간선의 가중치가 같을때는 BFS 알고리즘이 최단거리를 계산해주기에 BFS 알고리즘을 채택했다.
아래는 내가 작성한 풀이다.
결론 상근이 아싸. (결혼식에 오는 친구 총 3명 ..ㅠㅠ)
import * as fs from 'fs';
import * as path from 'path';
import {bindNodeCallback, from, Observable, of} from "rxjs/index";
import {concatMap, map} from "rxjs/internal/operators";
const executeFromLocal: boolean = true;
const inputPath: string = executeFromLocal ? path.resolve(__dirname, './source') : '/dev/stdin';
// 시간 복잡도: O(n+m)
// 공간 복잡도: O(m)
bindNodeCallback(fs.readFile)(inputPath).pipe(
concatMap((buffer: Buffer): Observable<number> => {
const root: number[][]= [];
const n = Number(buffer.toString('utf-8').split('\n')[0]);
const m = Number(buffer.toString('utf-8').split('\n')[1]);
const checked: number[] = [];
for (let i = 0; i <= n; i++) {
root[i] = [];
checked[i] = 0;
}
// 양방향 그래프 생성
for (let i = 0; i < m; i++) {
const [a, b] = [
Number(buffer.toString('utf-8').split('\n')[i+2].split(' ')[0]),
Number(buffer.toString('utf-8').split('\n')[i+2].split(' ')[1])
];
root[a].push(b);
root[b].push(a);
}
const startingPoint: number = 1;
const found = (startingPoint: number) => {
checked[startingPoint] = startingPoint;
let q: number[] = [startingPoint];
while (q.length > 0) {
let c: number = q.shift() as number;
root[c].forEach((way: number) => {
if (checked[way] == 0) {
// 다음 정점거리
checked[way] = checked[c] + 1;
console.log(Number(way));
q.push(Number(way));
}
});
}
return checked;
};
let tomodachiCount = 0;
const foundBros = found(startingPoint);
for(let i =2; i<=n; i++){
if(foundBros[i] == 2 || foundBros[i] == 3){
tomodachiCount++;
}
}
return of(tomodachiCount);
}),
).subscribe((tomodachiCount) => {
console.log('tomodachiCount', tomodachiCount);
});
영준 (=hax0r)
https://www.hax0r.info
I am a passionate back-end developer always in hunger of learning new things and sharing what i have learned. who loves challenges, newest technologies and programming at all.