[백준/nodeJS] 11375. 열혈강호 (이분매칭 문제)

안녕하세요. 박기린입니다.

백준 11375번 열혈강호 문제 풀어보겠습니다.

 

 

---

문제 링크

 

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

11375번: 열혈강호

 

 

 

 

---

문제 해석

이 문제는 이분 매칭에 대해서만 알면 쉽게 풀 수 있습니다.

 

이분 매칭에 대한 설명을 다른 분이 너무 쉽게 잘 적어주셔서, 링크를 적어놓겠습니다.

링크 : https://blog.naver.com/kks227/220807541506

이분 매칭(Bipartite Matching)

 

 

 

 

---

정답 코드

const fs = require("fs");
const [first, ...second] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, M] = first.split(" ").map(Number);

const SIZE = 1001;
const visited = new Array(SIZE); 
const match = new Array(SIZE).fill(-1);

let count = 0;

const graph = new Map();

for (let i = 0; i < N; i++) {
  const [_, ...works] = second[i].split(" ").map(Number);
  graph.set(i + 1, works);
}

const dfs = (v1) => {
  if (visited[v1]) return false;
  visited[v1] = true;
  for (v2 of graph.get(v1)) {
    if (match[v2] === -1 || dfs(match[v2])) {
      match[v2] = v1;
      return true;
    }
  }
  return false;
};

for (let i = 1; i <= N; i++) {
  visited.fill(false);
  if (dfs(i)) count++;
  // if (count === N) break;
}

console.log(count);

 

 

 

---

정답 코드 풀이

section1

const [N, M] = first.split(" ").map(Number);

const SIZE = 1001;
const visited = new Array(SIZE); // v1의 탐색 여부 저장
const match = new Array(SIZE).fill(-1); // v2와 연결된 v1의 주소 저장

let count = 0; // 매칭수

N : 직원 수

M : 일의 갯수

SIZE : N과 M의 최대 가능 갯수

 

visited : 직원 노드(v1)의 탐색 여부를 저장하는 Array.

match : 일 노드(v2)와 연결된 직원 노드(v1)의 번호를 저장하는 Array.

 

count : 이분 탐색의 결과로, 직원 노드(v1)과 일 노드(v2)가 최대한 매칭되는 수를 저장하는 변수. (출력 목표)

 

 

---

section2

const graph = new Map();

for (let i = 0; i < N; i++) {
  const [_, ...works] = second[i].split(" ").map(Number);
  graph.set(i + 1, works);
}

Map으로 그래프를 구현합니다.

 

{1번부터 N : i 번 사람이 할 수 있는 일}의 형태로 저장을 합니다.

ex: { 1번 사람 : [1번 작업, 2번 작업] }

 

 

 const [_, ...works] = second[i].split(" ").map(Number);

이 코드에서 '_'에 원래 들어올 값은, works의 길이입니다. 딱히 필요하지 않아서 '_' 처리를 했습니다.

 

 

 

---

section3

const dfs = (v1) => {
  if (visited[v1]) return false;
  visited[v1] = true;
  for (v2 of graph.get(v1)) {
    if (match[v2] === -1 || dfs(match[v2])) {
      // v2에 연결된 v1이 없는 경우 || 기존에 연결되어 있던 v1이 또 다른 v2와 연결이 가능한 경우
      match[v2] = v1;
      return true;
    }
  }
  return false;
};

dfs로 이분 탐색을 구현합니다.

v1은 사람, v2는 작업을 의미합니다.

 

 

 

  if (visited[v1]) return false;
  visited[v1] = true;

이미 탐색을 진행했던 사람이라면, dfs()를 실행하지 않습니다.

 

 

for (v2 of graph.get(v1)) {

v1번 사람이 가진 모든 v2 작업을 for - of 문을 통해서 접근합니다.

 

 

    if (match[v2] === -1 || dfs(match[v2])) {
      // v2에 연결된 v1이 없는 경우 || 기존에 연결되어 있던 v1이 또 다른 v2와 연결이 가능한 경우
      match[v2] = v1;
      return true;
    }

 

1. match[v2] === -1

현재 v2에 연결된 v1이 없는 경우,

 

2. dfs(match[v2])

현재 v2에 연결된 v1이, 또 다른 v2와 연결이 가능한 경우,

 

match[v2] = v1을 실행합니다. 즉, v2에 v1을 새롭게 연결합니다.

 

 

위 두 조건에 하나라도 통과한다면 true, 아니면 false를 return합니다.

이 과정 속에서 dfs(깊이우선탐색)가 일어납니다.

 

 

 

---

section4

for (let i = 1; i <= N; i++) {
  visited.fill(false); // 매번 방문여부를 초기화해야 함.
  if (dfs(i)) count++;
}

dfs를 1번부터 N번까지 차례대로 실행해줄 코드입니다.

 

 

 

const dfs = (v1) => {
  if (visited[v1]) return false;

dfs()는 vistied[v1]이 false일 때만 동작해서,

 

  visited.fill(false); // 매번 방문여부를 초기화해야 함.

위 코드로 매번 초기화를 해야 합니다.

 

 

 

  if (dfs(i)) count++;

1번부터 N번까지 dfs()를 돌린 후, true를 반환하면 count에 +1을 해줍니다.

 

 

 

---

section5

console.log(count);

마지막으로 count를 출력해주면 끝입니다.