Acmicpc 5567 풀이

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명 ..ㅠㅠ)

screen-shot

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);
});

About Me

Related Posts

What do you think?