[C++] 프로그래머스 - 표 병합

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

프로그래머스

<풀이>

1. 표를 편집하는 명령어를 입력받는다.

2. 명령어를 실행한 결과를 반환한다.

 

<해법>

1. 알고리즘 선택하기

=> 문제를 읽고 가장 먼저 Union-Find 알고리즘이 떠오릅니다. 아래는 Union-Find 알고리즘에 따라 구현 방법에 대해 정리한 생각입니다.

(1) 'UPDATE r c value'

: 표의 (r, c)의 부모를 찾아 value를 바꾼다.

(2) 'UPDATE value1 value2'

: 표의 모든 value1을 value2로 바꾼다. 표의 크기는 50x50 = 2500이고 명령어의 갯수는 최대 1000개이므로, O(2500x1000)의 시간복잡도로 풀이 가능하다.

(3) 'MERGE r1 c1 r2 c2'

: (r2, c2)의 부모를 (r1, c1)의 부모로 바꾼다. 데이터는 규칙에 따라 바꾼다.

(4) 'PRINT r c'

: (r, c)의 부모를 찾아 value를 출력한다.

(5) 'UNMERGE r c'

: 여기서 막힙니다. 표의 모든 셀과 (r, c)의 부모가 같은지 확인해야하는데, 이 경우 O(2500x2500x1000)의 시간복잡도가 되기 때문입니다(Union-Find의 find함수가 최악의 경우 O(N)이기 때문). 그렇다면 어떻게 해야할까요?

 

2. UNMERGE 해결하기

=> 생각해보면, Union-Find 알고리즘은 Union과 Find에만 관심이 있는 알고리즘입니다. 저희 문제와 같이 UNMERGE하는 부분에는 관심이 없습니다. 따라서, 이 알고리즘의 좋은 부분만 가져와 저희의 문제에 맞게 조금 변형해서 사용해야합니다. UNMERGE 명령어에서 가장 큰 문제점은 셀의 부모가 제 멋대로라는 점입니다.

위 그림처럼 부모를 찾기위해 계속해서 타고들어가야 하기 때문에 3,4,5번이 모두 1번 셀이라는 것을 단번에 알 수 없습니다. 그렇다면 3,4,5번이 모두 2번처럼 1로 표시되면 어떨까요? 정말 간단해집니다. 모든 셀을 돌며 부모가 1인것만 다시 되돌리면 되기 때문입니다. 그리고 이렇게 되면 O(2500x1000)의 시간복잡도가 되므로 풀 수 있습니다. 

 

3. MERGE 교체하기

=> 3,4,5번의 부모가 모두 1로 표현되려면, MERGE부터 바꿔야합니다. 기존 Union-Find의 경우는 부모만 바꾸어 주었다면, 저희는 부모의 자식들 또한 바꾸어주어야합니다.

위 그림처럼 교체하면 MERGE는 O(2500x1000)의 시간복잡도를 가지게 되므로 풀 수 있습니다.

 

4. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 셀은 1차원 배열로 바꿔서 생각한다. 부모를 정수로 편하게 관리할 수 있기 때문.

(2) 부모 배열과 데이터 배열 두 개를 관리한다.

(3) 빈 데이터는 "EMPTY"를 넣는다. 데이터는 알파벳 소문자와 숫자로만 이루어져있으므로 가능하고, 출력할 때 편리하다.

자세한 구현은 아래 코드를 참고해주세요.

 

#include <string>
#include <vector>
#include <sstream>
 
using namespace std;
 
int link[2501];
string value[2501];
 
int flatPos(int r, int c) {
    return (r - 1) * 50 + c;
}
 
vector<string> solution(vector<string> commands) {
    vector<string> answer;
 
    //초기화
    for (int i = 1; i <= 2500; i++) {
        link[i] = i;
        value[i] = "EMPTY";
    }
 
    //해법
    for (string &command : commands) {
        vector<string> v;
        stringstream ss(command);
        string token;
        while (ss >> token) v.push_back(token);
 
        if (v[0] == "UPDATE") {
            if (v.size() == 4) { //1. UPDATE r c value
                int pos = flatPos(stoi(v[1]), stoi(v[2]));
                string val = v[3];
                int parent = link[pos];
                value[parent] = val;
            }
            else { //2. UPDATE value1 value2
                string val1 = v[1], val2 = v[2];
                for (int i = 1; i <= 2500; i++) {
                    if (value[i] == val1) value[i] = val2;
                }
            }
        }
        else if (v[0] == "MERGE") { //3. MERGE r1 c1 r2 c2
            int pos1 = flatPos(stoi(v[1]), stoi(v[2])), pos2 = flatPos(stoi(v[3]), stoi(v[4]));
            int parent1 = link[pos1], parent2 = link[pos2];
            if (parent1 != parent2) {
                for (int i = 1; i <= 2500; i++) {
                    if (link[i] == parent2) link[i] = parent1;
                }
                string val1 = value[parent1], val2 = value[parent2];
                if (val1 == "EMPTY" && val2 != "EMPTY") {
                    value[parent1] = value[parent2];
                }
                else {
                    value[parent2] = value[parent1];
                }
            }
        }
        else if (v[0] == "UNMERGE") { //4. UNMERGE r c
            int pos = flatPos(stoi(v[1]), stoi(v[2]));
            int parent = link[pos];
            string val = value[parent];
            for (int i = 1; i <= 2500; i++) {
                if (link[i] == parent) {
                    link[i] = i;
                    value[i] = "EMPTY";
                }
            }
            value[pos] = val;
        }
        else { //5. PRINT r c
            int pos = flatPos(stoi(v[1]), stoi(v[2]));
            int parent = link[pos];
            answer.push_back(value[parent]);
        }
    }
 
    return answer;
}

 

Union-Find에 대해 알아볼 수 있는 문제였습니다.