[1일 1알고] 표 병합

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

프로그래머스

1일 1알고라고 이름을 정해놓고서 매일 올리지 못하고 있네요 오늘은 union-find를 응용하는 문제입니다.

 

표가 주어지고 이에대한 명령어를 수행하는 문제입니다.

 

명령어로는 UPDATE, MERGE, UNMERGE가 있습니다.

 

다행히도 표가 50x50 크기로 정해져있기 때문에 UPDATE를 할 때 완전탐색을 하더라도 시간적으로 문제는 없을 것입니다.

다만 MERGE, UNMERGE는 그룹의 전체를 바꾸는 것이기 때문에 어떻게 해결할지에대한 솔루션이 필요합니다.

 

따라서 그룹을 다루는 알고리즘인 union find를 사용합니다.

merge를 할 때 union을 한다면 셀을 쉽게 합칠 수 있을 것이고, unmerge를 할 때는 같은 parent라면 unmerge를 하는 식으로 하면 될듯합니다.

---

        stringstream ss(command);
        vector<string> tokens;
        string temp;
        while (ss >> temp)
        {
            tokens.push_back(temp);
        }

일단 들어온 각 command에 대해 stringstream으로 파싱을 진행합니다.

 

이후 token을 통해 명령어를 실행합니다.

 

int Get1DPoint(int r, int c)
{
    return (r - 1) * 50 + (c - 1);
}

int FindParent(int x)
{
    if (x == parent[x])
        return x;

    return parent[x] = FindParent(parent[x]);
}

Get1DPoint(GetIndex)는 2차원 좌표를 1차원 좌표로 바꾸는 간단한 함수입니다.

 

FindParent는 union-find에서 사용하고는 하는 find함수입니다.

 

if (tokens[0] == "UPDATE")
{
    // r c의 값을 value로 변경
    if (tokens.size() == 4)
    {
        int r = stoi(tokens[1]);
        int c = stoi(tokens[2]);

        int index = Get1DPoint(r, c);
        int root = FindParent(index);
        
        values[root] = tokens[3];
    }
    // value1을 가지는 모든 cell을 value2로 변경
    else
    {
        for (int i = 0; i < 2500; ++i)
        {
            int root = FindParent(i);

            if (values[root] == tokens[1])
            {
                values[root] = tokens[2];
            }
        }
    }
}

update는 두가지 명령으로 나눠집니다.

1. (r, c)의 값을 value로 변경

2. value1을 가지고 있는 모든 cell을 value2로 변경하는 것입니다.

 

1번은 (r, c)의 위치를 대표하는 parent를 찾고 해당 위치의 값을 변경하면 됩니다.

2번은 모든 셀을 순회하며 해당하는 값을 변경합니다.

 

---

void MergeCell(int r1, int c1, int r2, int c2)
{
    int idx1 = Get1DPoint(r1, c1);
    int idx2 = Get1DPoint(r2, c2);

    int p1 = FindParent(idx1);
    int p2 = FindParent(idx2);
    if (p1 == p2)
        return;

    string v1 = values[p1];
    string v2 = values[p2];

    string mergeValue;
    if (v1 == "")
    {
        mergeValue = v2;
    }
    else
    {
        mergeValue = v1;
    }

    parent[p2] = p1;
    values[p1] = mergeValue;
    values[p2] = "";
}

MergeCell의 경우 (r1, c1) (r2, c2)위치의 셀을 합치며, 둘다 값이 있다면 (r1, c1)을 하나만 가진다면 해당 셀의 값을 가지게 됩니다.

 

이를 위해 먼저 각 좌표의 parent를 찾고 parent value에 따라 수정해줍니다.

value를 어디에 넣을지는 선택하면 되겠습니다.

---

void UnmergeCell(int r, int c)
{
    int target = Get1DPoint(r, c);
    int root = FindParent(target);

    string savedValue = values[root];

    vector<int> group;

    for (int i = 0; i < 2500; i++)
    {
        if (FindParent(i) == root)
        {
            group.push_back(i);
        }
    }

    for (int idx : group)
    {
        parent[idx] = idx;
        values[idx] = "";
    }

    values[target] = savedValue;
}

unmerge의 경우 r, c가 포함된 셀을 unmerge합니다. 값은 r, c를 제외한 모두 ""로 만들기 때문에

같은 group을 찾고 이후에 이에 대해 초기화 해줍니다.