[프로그래머스/C++] 표 병합 (2023 KAKAO BLIND RECRUITMENT)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

표 병합 문제에서 중요한 명령어는 MERGE와 UNMERGE다.

 

다른 명령어들은 vector를 이용하면 바로 수행할 수 있지만, MERGE나 UNMERGE된 셀일 수 있기 때문에 이를 파악하는게 중요하다.

 

이 문제를 풀기 위해 union-find 알고리즘을 이용했다.

예를 들어 (1, 1) 셀과 (2, 2) 셀이 병합 되었다고 가정하자.

이 경우 (2, 2) 셀은 (1, 1)셀의 집합에 포함되어 있다고 표시를 한다면, (2, 2)셀의 값을 업데이트 하거나 변경할 경우 (2, 2)셀의 집합의 값을 변경하면 문제가 해결된다.

 

UNMERGE는 반대로 한 집합에 속한 모든 원소들을 초기화 시키고 마지막에 명령어에 있는 cell에만 저장된 표의 값을 입력하면 된다.

 

문제 자체는 어렵지 않지만 MERGE와 UNMERGE를 구현하는 게 생각보다 오래 걸렸다.

 

집합을 표시하기 위해 어떤 집합에 속해있는지를 나타내는 parents라는 vector를 만들고, 집합에 속해 있는 원소들을 저장할 childs라는 vector를 만들어 관리했다.

그리고 표의 값을 저장할 cell이라는 vector를 이용해 어떤 단어가 표에 저장되어 있는지 기록했다.

 

 

​

[아이디어 정리]

1. union-find 알고리즘으로 MERGE일 경우 하나의 집합으로 만든다.
2. UNMERGE일 경우 그 집합에 속해 있던 모든 표를 초기화 한다. (명령어 Row Col에 해당하는 셀 제외)
3. UPDATE가 일어날 경우 그 집합에 들어있는 대표 단어를 바꾼다. 
4. PRINT는 집합의 대표 단어를 PRINT한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;

vector<string> solution(vector<string> commands) {
    vector<string> answer;
    vector<vector<string>> cell(51,vector<string>(51));
    vector<vector<pair<int,int>>>parents(51,vector<pair<int,int>>(51));
    vector<vector<set<pair<int,int>>>>childs(51,vector<set<pair<int,int>>>(51));
    pair<int,int>np;
    int r, c;
    for (int i=1; i<51; i++)
    {
        for (int j=1; j<51; j++)
        {
            np.first=i,np.second=j;
            parents[i][j]=np;            
        }
    }
    set<pair<int,int>>::iterator it;
    for (int i=0; i<commands.size();i++)
    {
        istringstream ss1(commands[i]);
        string buffer;
        vector<string> nowS;
        while (getline(ss1,buffer,' '))
        {
            nowS.push_back(buffer);
        }
        if (nowS[0]=="UPDATE")
        {
            if (nowS.size()==4)
            {
                r=stoi(nowS[1]), c=stoi(nowS[2]);
                np=parents[r][c];
                cell[np.first][np.second]=nowS[3];
            }
            else
            {
                for (int j=1; j<51; j++)
                {
                    for (int k=1; k<51; k++)
                    {
                        if (cell[j][k]==nowS[1])
                        {
                            cell[j][k]=nowS[2];
                        }
                    }
                }
            }
        }
        else if (nowS[0]=="MERGE")
        {
            int r1,c1, r2,c2, nr,nc, nr1,nc1;
            pair<int,int> p1, p2;
            r1=stoi(nowS[1]), c1=stoi(nowS[2]), r2=stoi(nowS[3]),c2=stoi(nowS[4]);
            p1=parents[r1][c1],p2=parents[r2][c2]; //p2를 전부 p1으로
            if (cell[p1.first][p1.second]=="")
            {
                cell[p1.first][p1.second]=cell[p2.first][p2.second];
            }
            set<pair<int,int>> ss=childs[p2.first][p2.second];
            parents[p2.first][p2.second].first=p1.first;
            parents[p2.first][p2.second].second=p1.second;
            childs[p1.first][p1.second].insert(p2);       
            for (it=ss.begin(); it!=ss.end(); it++)
            {
                np=*it;
                parents[np.first][np.second].first=p1.first;
                parents[np.first][np.second].second=p1.second;
                childs[p1.first][p1.second].insert(np);
            }            
        }
        else if (nowS[0]=="UNMERGE")
        {
            r=stoi(nowS[1]), c=stoi(nowS[2]);
            np=parents[r][c]; //부모
            string ns=cell[np.first][np.second];
            set<pair<int,int>> ss=childs[np.first][np.second]; //모든 자식리스트
            childs[np.first][np.second]=set<pair<int,int>>(); //부모 자식 초기화
            cell[np.first][np.second]=""; //부모 초기화
            for (it=ss.begin(); it!=ss.end(); it++) //부모 자식리스트 전부 초기화
            {
                np=*it;
                parents[np.first][np.second].first=np.first;
                parents[np.first][np.second].second=np.second;
                childs[np.first][np.second]=set<pair<int,int>>();
                cell[np.first][np.second]="";
            } 
            cell[r][c]=ns;
        }
        else
        {
            r=stoi(nowS[1]), c=stoi(nowS[2]);
            np=parents[r][c];
            if (cell[np.first][np.second]=="")
            {
                answer.push_back("EMPTY");
            }
            else
            {
                answer.push_back(cell[np.first][np.second]);
            }
        }
    }
    
    
    return answer;
}

 

---

문제를 대충 읽고 풀다가 왜 오류가 생겼는지 모를 뻔 했다...

이것저것 하면서 풀다가 보니 오래 걸렸네...

프로그래머스