백준 / 4195번 / 친구 네트워크 / JS

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

 

풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? 0 : './input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const T = +input.shift();

function* idGenerator() {
  let id = 0;

  while (true) {
    yield id++;
  }
}

class UnionFind {
  constructor() {
    this.parent = [];
    this.count = [];
    this.nameMap = new Map();
    this.idGenerator = idGenerator();
  }

  getId(name) {
    if (!this.nameMap.has(name)) {
      const newId = this.idGenerator.next().value;

      this.nameMap.set(name, newId);
      this.parent.push(newId);
      this.count.push(1);
    }

    return this.nameMap.get(name);
  }

  getParent(id) {
    if (this.parent[id] === id) {
      return id;
    }

    return (this.parent[id] = this.getParent(this.parent[id]));
  }

  union(id1, id2) {
    const rootId1 = this.getParent(id1);
    const rootId2 = this.getParent(id2);

    if (rootId1 === rootId2) {
      return this.count[rootId1];
    }

    if (this.count[rootId1] < this.count[rootId2]) {
      this.parent[rootId1] = rootId2;
      this.count[rootId2] += this.count[rootId1];
    } else {
      this.parent[rootId2] = rootId1;
      this.count[rootId1] += this.count[rootId2];
    }

    return this.count[this.getParent(id1)];
  }
}

function solution() {
  const result = [];

  for (let testCase = 0; testCase < T; testCase++) {
    const F = +input.shift();
    const uf = new UnionFind();

    for (let i = 0; i < F; i++) {
      const [user1, user2] = input.shift().split(' ');

      const user1Id = uf.getId(user1);
      const user2Id = uf.getId(user2);

      const count = uf.union(user1Id, user2Id);

      result.push(count);
    }
  }

  console.log(result.join('\n'));
}

solution();

Union Find를 활용하는 문제였다.

기본 Union Find와 다른 점은, 문자열로 입력을 받기 때문에 그에 해당하는 숫자를 만들어주어야 했다.

그래야 기존 배열에서 인덱스로 바로 접근 가능하도록 하는 구현이 가능하기 때문이다.

 

`idGenerator()`

function* idGenerator() {
  let id = 0;

  while (true) {
    yield id++;
  }
}

입력받는 문자열 이름의 숫자 id를 만들어주는 제너레이터 함수이다.

사실 id를 전역 변수로 만든 후에, 일반 함수로 만들어서 써도 상관은 없지만

제너레이터 함수를 써본적이 없어서 이번에 한 번 써보기로 했다.

 

간단히 설명하자면, 제너레이터 함수는 함수를 선언하는 것도 약간 다른데,

' * ' 문자를 붙여줘야 한다.

그리고 하나의 값을 반환하는 것이 아니라, 여러 개의 값을 필요에 따라 반환할 수 있다.

`next()` 메서드를 부를 때 마다 가장 가까운 yield 문을 만날 때까지 실행이 된다.

`next()`는 `value`와 `done`을 가지는 객체를 반환한다.

 

자세한 건 아래에서!

https://ko.javascript.info/generators

제너레이터

 

`class UnionFind`

다음으로 문제 풀이에 필요한 Union Find에 관련된 것을 한 군데서 관리하기 위해 클래스를 만들어주었다.

class UnionFind {
  constructor() {
    this.parent = [];
    this.count = [];
    this.nameMap = new Map();
    this.idGenerator = idGenerator();
  }

  getId(name) {
    if (!this.nameMap.has(name)) {
      const newId = this.idGenerator.next().value;

      this.nameMap.set(name, newId);
      this.parent.push(newId);
      this.count.push(1);
    }

    return this.nameMap.get(name);
  }

  getParent(id) {
    if (this.parent[id] === id) {
      return id;
    }

    return (this.parent[id] = this.getParent(this.parent[id]));
  }

  union(id1, id2) {
    const rootId1 = this.getParent(id1);
    const rootId2 = this.getParent(id2);

    if (rootId1 === rootId2) {
      return this.count[rootId1];
    }

    if (this.count[rootId1] < this.count[rootId2]) {
      this.parent[rootId1] = rootId2;
      this.count[rootId2] += this.count[rootId1];
    } else {
      this.parent[rootId2] = rootId1;
      this.count[rootId1] += this.count[rootId2];
    }

    return this.count[this.getParent(id1)];
  }
}

 

`UnionFind.constructor()`

  constructor() {
    this.parent = [];
    this.count = [];
    this.nameMap = new Map();
    this.idGenerator = idGenerator();
  }

UnionFind 클래스를 만드는 생성자 함수이다.

각 초기변수가 의미하는 것은 다음과 같다.

• parent : 각 요소의 부모 id를 나타내는 배열
• count : 현재 id가 속한 네트워크의 친구 수를 저장하는 배열
• nameMap : key는 이름, value는 id를 가지는 Map
• idGenerator : 위에서 선언한 id 제너레이터 함수

`UnionFind.getId(name)`

  getId(name) {
    if (!this.nameMap.has(name)) {
      const newId = this.idGenerator.next().value;

      this.nameMap.set(name, newId);
      this.parent.push(newId);
      this.count.push(1);
    }

    return this.nameMap.get(name);
  }

이름을 인자로 받아 해당 이름에 해당하는 id를 반환해주는 함수이다.

코드를 보면 `next()`를 호출하면 제너레이터 함수의 다음 yield를 만나고,

그 때 해당하는 value값을 얻을 수 있다.

제너레이터 함수에서 whie(true)로 무한 반복을 하고 있기 때문에,

1씩 증가된 id를 `next()`로 부르면 계속 생성할 수 있다.

 

만약 `nameMap`에 인자로 들어온 이름이 없다면,

`nameMap`에 이름과 생성한 아이디를 넣어주고,

`parent`에 생성한 id를 넣어준다.

이 때, 배열의 인덱스와 id 모두 0부터 시작하기 때문에,

기본 Union Find 문제 풀 때 처럼 자기 인덱스를 값으로 가지는 배열을 생성하는 것과 같다.

그 후, 초기에는 네트워크에 본인만 있으므로, `count`에 1을 넣어준다.

 

마지막으로 id를 반환해준다.

 

`UnionFind.getParent(id)`

  getParent(id) {
    if (this.parent[id] === id) {
      return id;
    }

    return (this.parent[id] = this.getParent(this.parent[id]));
  }

인자로 id를 받고, 해당 id의 루트 부모를 찾아주는 함수이다.

기본 Union Find의 함수와 똑같이 구현하면 된다.

 

`UnionFind.union(id1, id2)`

  union(id1, id2) {
    const rootId1 = this.getParent(id1);
    const rootId2 = this.getParent(id2);

    if (rootId1 === rootId2) {
      return this.count[rootId1];
    }

    if (this.count[rootId1] < this.count[rootId2]) {
      this.parent[rootId1] = rootId2;
      this.count[rootId2] += this.count[rootId1];
    } else {
      this.parent[rootId2] = rootId1;
      this.count[rootId1] += this.count[rootId2];
    }

    return this.count[this.getParent(id1)];
  }
}

합칠 id 두 개를 인자로 받아, 하나로 합쳐주는 함수이다.

 

주의할 점은 두 id의 부모가 같을 때이다.

이미 부모가 같으면 합쳐져있다는 의미이므로, 한 쪽의 수를 더하는 행위를 할 필요가 없다.

따라서 아무 부모의 수를 반환해주면 된다.

 

그 외에는 대소비교를 해서 한쪽에 합쳐주면된다.

 

`solution()`

function solution() {
  const result = [];

  for (let testCase = 0; testCase < T; testCase++) {
    const F = +input.shift();
    const uf = new UnionFind();

    for (let i = 0; i < F; i++) {
      const [user1, user2] = input.shift().split(' ');

      const user1Id = uf.getId(user1);
      const user2Id = uf.getId(user2);

      const count = uf.union(user1Id, user2Id);

      result.push(count);
    }
  }

  console.log(result.join('\n'));
}

solution();

메인 함수에서는 위에서 만든 클래스를 잘 활용해 답을 구해주면 된다.

주의할 것은 테스트케이스가 여러개이기 때문에 초기화를 잘 해줘야 한다.