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

프로그래머스 표 병합

프로그래머스

문제

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value"
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "PRINT r c"
   • (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
   • 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

commands 효과

UPDATE 1 1 menu	(1,1)에 "menu" 입력
UPDATE 1 2 category	(1,2)에 "category" 입력
UPDATE 2 1 bibimbap	(2,1)에 "bibimbap" 입력
UPDATE 2 2 korean	(2,2)에 "korean" 입력
UPDATE 2 3 rice	(2,3)에 "rice" 입력
UPDATE 3 1 ramyeon	(3,1)에 "ramyeon" 입력
UPDATE 3 2 korean	(3,2)에 "korean" 입력
UPDATE 3 3 noodle	(3,3)에 "noodle" 입력
UPDATE 3 4 instant	(3,4)에 "instant" 입력
UPDATE 4 1 pasta	(4,1)에 "pasta" 입력
UPDATE 4 2 italian	(4,2)에 "italian" 입력
UPDATE 4 3 noodle	(4,3)에 "noodle" 입력

위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

commands 효과

MERGE 1 2 1 3	(1,2)와 (1,3) 병합
MERGE 1 3 1 4	(1,3)과 (1,4) 병합

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

commands 효과

UPDATE korean hansik	"korean"을 "hansik"으로 변경
UPDATE 1 3 group	(1,3) 위치의 셀 값을 "group"으로 변경

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

commands 효과

UNMERGE 1 4

셀 병합 해제 후 원래 값은 (1,4)가 가짐

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

알고리즘 아이디어

• 병합을 할 때, 중요한 것은 대표 셀이 정해져야 한다.
• 그러나, 매번 병합을 할 때마다 이 대표 셀을 찾아서 저장해야 한다.
• 이 기능을 Union-Find로 구현한다.

Union-Find 개념 적용

각 셀을 자신의 부모 셀을 가리키는 구조로 유지합니다.

1. find 함수: 현재 셀이 속한 그룹의 대표 셀을 찾습니다.
2. union 함수: 두 셀을 병합하여 하나의 대표 셀을 공유하게 만듭니다.
3. unmerge 함수: 해당 그룹의 모든 셀을 원래 상태로 되돌립니다.

각 셀의 값을 저장하는 배열을 따로 두고, 병합된 경우 대표 셀의 값을 유지합니다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

struct xy {
    int x, y;
};

vector<string> split(string input, char dim) {
    stringstream ss(input);
    vector<string> result;
    string stringbuffer;
    
    while (getline(ss, stringbuffer, dim)) {
        result.push_back(stringbuffer);
    }
    return result;
}

xy findParent(vector<vector<xy>>& parent, int x, int y) {
    if (parent[x][y].x == x && parent[x][y].y == y) {
        return {x, y};
    }
    return parent[x][y] = findParent(parent, parent[x][y].x, parent[x][y].y);
}

void mergeCells(int x1, int y1, int x2, int y2, 
                vector<vector<xy>>& parent, vector<vector<string>>& rule) {
    xy root1 = findParent(parent, x1, y1);
    xy root2 = findParent(parent, x2, y2);
    
    if (root1.x == root2.x && root1.y == root2.y) return;

    parent[root2.x][root2.y] = root1;

    if (rule[root1.x][root1.y] == "" && rule[root2.x][root2.y] != "") {
        rule[root1.x][root1.y] = rule[root2.x][root2.y];
    }
}

void unmergeCells(int x, int y, vector<vector<xy>>& parent, vector<vector<string>>& rule) {
    xy root = findParent(parent, x, y);
    string value = rule[root.x][root.y];

    vector<xy> toReset;
    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= 50; j++) {
            xy find = findParent(parent, i, j);
            if (find.x == root.x && find.y == root.y) {
                toReset.push_back({i, j});
            }
        }
    }

    for (xy c : toReset) {
        parent[c.x][c.y] = {c.x, c.y};
        rule[c.x][c.y] = "";
    }

    rule[x][y] = value;
}

vector<string> solution(vector<string> commands) {
    vector<string> answer;
    vector<vector<string>> rule(51, vector<string>(51, ""));
    vector<vector<xy>> parent(51, vector<xy>(51));

    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= 50; j++) {
            parent[i][j] = {i, j};
        }
    }

    for (string command : commands) {
        vector<string> temp = split(command, ' ');

        if (temp[0] == "UPDATE") {
            if (temp.size() == 4) {
                int x = stoi(temp[1]);
                int y = stoi(temp[2]);
                xy parentCell = findParent(parent, x, y);
                rule[parentCell.x][parentCell.y] = temp[3];
            } else {
                for (int i = 1; i <= 50; i++) {
                    for (int j = 1; j <= 50; j++) {
                        if (rule[i][j] == temp[1]) {
                            rule[i][j] = temp[2];
                        }
                    }
                }
            }
        } 
        else if (temp[0] == "MERGE") {
            int x1 = stoi(temp[1]);
            int y1 = stoi(temp[2]);
            int x2 = stoi(temp[3]);
            int y2 = stoi(temp[4]);
            mergeCells(x1, y1, x2, y2, parent, rule);
        } 
        else if (temp[0] == "UNMERGE") {
            int x = stoi(temp[1]);
            int y = stoi(temp[2]);
            unmergeCells(x, y, parent, rule);
        } 
        else if (temp[0] == "PRINT") {
            int x = stoi(temp[1]);
            int y = stoi(temp[2]);
            xy parentCell = findParent(parent, x, y);
            if (rule[parentCell.x][parentCell.y] == "") {
                answer.push_back("EMPTY");
            } else {
                answer.push_back(rule[parentCell.x][parentCell.y]);
            }
        }
    }

    return answer;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!