프로그래머스: 표 병합 - javascript(Union-Find)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/150366

프로그래머스

 

문제 풀이 힌트 

이 문제는 명령어에 따라 51x51 크기의 셀 값을 업데이트하거나 병합하는 작업을 수행하는 것입니다.

각 셀의 부모 좌표를 저장하여 병합된 셀들을 추적하고, 부모 좌표가 동일한 셀들은 같은 값으로 업데이트됩니다.

 

문제는 유니온-파인드 (Union-Find) 알고리즘을 사용하여 해결됩니다.

: 유니온-파인드 알고리즘은 집합의 합병(Union)과 특정 원소가 속한 집합의 대표 원소를 찾는(Find) 기능을 효율적으로 수행하는 알고리즘입니다. 이 알고리즘의 핵심 요소는 다음과 같습니다:

1. 초기화: 각 셀을 자신이 속한 집합의 유일한 원소로 초기화하고, 각 셀의 부모를 자기 자신으로 설정합니다.
2. Find: 특정 셀의 부모를 찾아 반환합니다. 이는 경로 압축(path compression)을 사용하여, 셀의 부모를 직접 최상위 부모로 설정함으로써 탐색 속도를 높입니다.
3. Union: 두 셀을 병합하여 같은 집합에 속하게 합니다. 이는 두 셀의 부모를 동일하게 설정하는 것으로 구현됩니다.
4. Update: 특정 셀의 값을 변경하거나 병합된 셀들의 값을 동기화합니다.
5. Print: 특정 셀의 값을 출력합니다.

이 문제에서는 각 명령어에 따라 유니온-파인드 알고리즘을 활용하여 셀을 병합하거나 분리하고, 셀의 값을 효율적으로 관리합니다.

 

정답 풀이 코드 

function solution(commands) {
  let answer = []; // 결과를 저장할 배열
  const cell = Array(51) // 51x51 크기의 2차원 배열을 생성하고 초기값을 빈 문자열로 채움
    .fill()
    .map((_) => Array(51).fill(''));
  const parent = Array(51) // 각 셀의 부모 좌표를 저장할 2차원 배열을 생성
    .fill()
    .map((_, i) =>
      Array(51)
        .fill()
        .map((_, j) => [i, j])
    );

  for (const commandStr of commands) {
    // 명령어 리스트를 순회
    const [command, ...rest] = commandStr.split(' '); // 명령어와 매개변수를 분리
    switch (command) {
      case 'UPDATE':
        // UPDATE 명령어 처리
        if (rest.length === 3) update(rest); // 좌표와 값을 받아 업데이트
        else replace(rest); // 값을 받아 다른 값으로 변경
        break;
      case 'MERGE':
        merge(rest); // MERGE 명령어 처리
        break;
      case 'UNMERGE':
        unmerge(rest); // UNMERGE 명령어 처리
        break;
      case 'PRINT':
        answer = [...answer, print(rest)]; // PRINT 명령어 처리
        break;
    }
  }

  return answer; // 결과 반환

  function update(param) {
    const [r, c, value] = param; // 좌표와 값을 분리
    const target = find([r, c]); // 해당 좌표의 부모 좌표를 찾음
    iterateAll((i, j) => {
      // 모든 셀을 순회하며 부모 좌표가 동일한 셀을 찾음
      if (isSameCoords(parent[i][j], target)) cell[i][j] = value; // 동일한 부모를 가진 셀의 값을 업데이트
    });
  }

  function replace(param) {
    const [value1, value2] = param; // 변경할 값과 변경될 값을 분리

    iterateAll((i, j) => {
      // 모든 셀을 순회하며 값을 변경
      if (cell[i][j] === value1) cell[i][j] = value2;
    });
  }

  function merge(param) {
    const [r1, c1, r2, c2] = param; // 두 좌표를 분리
    if (r1 === r2 && c1 === c2) return; // 두 좌표가 동일하면 리턴

    const value = cell[r1][c1] !== '' ? cell[r1][c1] : cell[r2][c2]; // 값을 설정
    const parent1 = find([r1, c1]); // 첫 번째 좌표의 부모 좌표를 찾음
    const parent2 = find([r2, c2]); // 두 번째 좌표의 부모 좌표를 찾음

    if (!isSameCoords(parent1, parent2)) {
      parent[r2][c2] = parent1; // 부모 좌표가 다르면 두 번째 좌표의 부모를 첫 번째 부모로 설정
    }

    iterateAll((i, j) => {
      // 모든 셀을 순회
      if (isSameCoords(parent[i][j], parent2)) {
        parent[i][j] = parent1; // 부모 좌표를 변경
      }
      if (isSameCoords(parent[i][j], parent1)) {
        cell[i][j] = value; // 값을 설정
      }
    });
  }

  function unmerge(param) {
    const [r, c] = param; // 좌표를 분리
    const value = cell[r][c]; // 값을 저장
    const target = find([r, c]); // 부모 좌표를 찾음

    iterateAll((i, j) => {
      // 모든 셀을 순회
      if (isSameCoords(parent[i][j], target)) {
        cell[i][j] = ''; // 값을 초기화
        parent[i][j] = [i, j]; // 부모 좌표를 초기화
      }
    });

    cell[r][c] = value; // 원래 값을 복원
  }

  function print(param) {
    const [r, c] = param; // 좌표를 분리

    return cell[r][c] === '' ? 'EMPTY' : cell[r][c]; // 셀 값 반환
  }

  function find(coord) {
    const [r, c] = coord; // 좌표를 분리

    if (isSameCoords([r, c], parent[r][c])) {
      return [Number(r), Number(c)]; // 부모 좌표가 자신이면 반환
    }

    parent[r][c] = find(parent[r][c]); // 재귀적으로 부모 좌표를 찾음

    return parent[r][c]; // 부모 좌표 반환
  }

  function isSameCoords(coord1, coord2) {
    return coord1.toString() === coord2.toString(); // 두 좌표가 같은지 비교
  }

  function iterateAll(callbackFn) {
    for (let i = 0; i < 51; i++) {
      for (let j = 0; j < 51; j++) {
        callbackFn(i, j); // 모든 셀에 대해 콜백 함수 실행
      }
    }
  }
}

 

Only 풀이 코드 

function solution(commands) {
  let answer = [];
  const cell = Array(51)
    .fill()
    .map((_) => Array(51).fill(''));
  const parent = Array(51)
    .fill()
    .map((_, i) =>
      Array(51)
        .fill()
        .map((_, j) => [i, j])
    );

  for (const commandStr of commands) {
    const [command, ...rest] = commandStr.split(' ');
    switch (command) {
      case 'UPDATE':
        if (rest.length === 3) update(rest);
        else replace(rest);
        break;
      case 'MERGE':
        merge(rest);
        break;
      case 'UNMERGE':
        unmerge(rest);
        break;
      case 'PRINT':
        answer = [...answer, print(rest)];
        break;
    }
  }

  return answer;

  function update(param) {
    const [r, c, value] = param;
    const target = find([r, c]);
    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], target)) cell[i][j] = value;
    });
  }

  function replace(param) {
    const [value1, value2] = param;

    iterateAll((i, j) => {
      if (cell[i][j] === value1) cell[i][j] = value2;
    });
  }

  function merge(param) {
    const [r1, c1, r2, c2] = param;
    if (r1 === r2 && c1 === c2) return;

    const value = cell[r1][c1] !== '' ? cell[r1][c1] : cell[r2][c2];
    const parent1 = find([r1, c1]);
    const parent2 = find([r2, c2]);

    if (!isSameCoords(parent1, parent2)) {
      parent[r2][c2] = parent1;
    }

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], parent2)) {
        parent[i][j] = parent1;
      }
      if (isSameCoords(parent[i][j], parent1)) {
        cell[i][j] = value;
      }
    });
  }

  function unmerge(param) {
    const [r, c] = param;
    const value = cell[r][c];
    const target = find([r, c]);

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], target)) {
        cell[i][j] = '';
        parent[i][j] = [i, j];
      }
    });

    cell[r][c] = value;
  }

  function print(param) {
    const [r, c] = param;

    return cell[r][c] === '' ? 'EMPTY' : cell[r][c];
  }

  function find(coord) {
    const [r, c] = coord;

    if (isSameCoords([r, c], parent[r][c])) {
      return [Number(r), Number(c)];
    }

    parent[r][c] = find(parent[r][c]);

    return parent[r][c];
  }

  function isSameCoords(coord1, coord2) {
    return coord1.toString() === coord2.toString();
  }

  function iterateAll(callbackFn) {
    for (let i = 0; i < 51; i++) {
      for (let j = 0; j < 51; j++) {
        callbackFn(i, j);
      }
    }
  }
}