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

분명히 맞게 푼 것 같았는데, 

10번 13번 14번에서 실패가 나왔다.

MERGE에서 같은 셀일때만 예외 처리를 했었는데,

같은 셀일때뿐만 아니라 이미 병합된 셀일때 예외 처리를 해야한다!

 

제일 먼저 작업한 것은 command에 맞춰 수행하는 함수를 구현했다.

"UPDATE r c" 일때는 updatePosition()

"UPDATE value1 value2"일 때는 updateValue()

"MERGE r1 c1 r2 c2"일 때는 mergeCell()

"UNMERGE r c"일 때는 unmergeCell()

"PRINT r c"일 때는 printCell()

 

여기서 가장 고려해야될 사항은 merge와 unmerge이다.

merge와 unmerge를 구현하기 위해서

parent라는 이차원 배열을 만들어서 초기값은 모두 자신의 위치를 갖게했다.

ex) parent[1][2] = { 1, 2}

 

merge가 수행되면 parent를 업데이트한다.

merge에서 값은 parent[x1][y1]의 위치와 parent[x2][y2]를 기준으로 확인하는데

그 이유는 merge가 안 된 데이터라면 자기 위치의 값을 알려줄 것이고,

merge가 된 데이터라면 merge된 셀 중 값을 갖고 있는 최상위 위치를 알려줄 것이기 때문이다.

 

x1,y1과 x2,y2의 최상위 위치가 동일하면,

이미 둘은 merge된 데이터므로 merge를 수행하지 않는다.

 

x1,y1의 최상위 위치 값이 EMPTY이면(x1,y1가 merge된 셀이 EMPTY)

x2,y2의 값을 기준으로 merge된다.

 

그 외의 경우에는 x1,y1의 값을 기준으로 merge된다.

 

unmerge는 x, y와 같은 최상위 위치를 갖고있는 모든 값들을

EMPTY로 하고 parent는 자기 자신을 가리키게 하고,

원래 값은 x,y 위치에 저장한다.

 

 

union-find와 유사하게 풀리는 문제이고,

사이즈가 50*50밖에 되지 않아,

parent를 찾을때나, 수정할때 이중탐색으로 구현하였다.

 

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

using namespace std;

vector<vector<string>> board(100,vector<string>(51, "EMPTY"));
vector<vector<pair<int,int>>> parent(51,vector<pair<int,int>>(51));

void updatePosition(int x, int y, string v){
  board[parent[x][y].first][parent[x][y].second] = v;
}
void updateValue(string prevV, string nextV){
  for(int i=1; i<51; i++){
    for(int j=1; j<51; j++){
      if(board[i][j] == prevV){
        board[i][j] = nextV;
      }
    }
  }
}

void mergeCell(int x1, int y1, int x2, int y2){
  pair<int, int> r1 = parent[x1][y1];
  pair<int, int> r2 = parent[x2][y2];
  if(r1 == r2){
    return;
  }
  if(board[r1.first][r1.second] == "EMPTY" ){
    for(int i=1; i<51; i++){
      for(int j=1; j<51; j++){
        if(parent[i][j] == r1){
          parent[i][j] = r2;
        }
      }
    }
  }//앞의 값이 비어있을때
  else{
    for(int i=1; i<51; i++){
      for(int j=1; j<51; j++){
        if(parent[i][j] == r2){
          parent[i][j] = r1;
        }
      }
    }
  }
}
void unmergeCell(int x, int y){
  string v = board[parent[x][y].first][parent[x][y].second];
  pair<int,int> p = parent[x][y];
  for(int i=1; i<51; i++){
    for(int j=1; j<51; j++){
      if(parent[i][j] == p){
        board[i][j] = "EMPTY";
        parent[i][j] = make_pair(i,j);
      }
    }
  }
  board[x][y] = v;
}
string printCell(int x, int y){
  return board[parent[x][y].first][parent[x][y].second];
}
vector<string> solution(vector<string> commands) {
    vector<string> answer;
    for(int i=1; i<51; i++){
      for(int j=1; j<51; j++){
        parent[i][j] = make_pair(i,j);
      }
    }
    for(auto command : commands){
      vector<string> cmd;
      string cmdBuffer = ""; 
      istringstream ss(command);
      while(getline(ss, cmdBuffer,' ')){
        cmd.push_back(cmdBuffer);
      }
      if(cmd[0] == "UPDATE"){
        if(cmd.size() == 4)
          updatePosition(stoi(cmd[1]),stoi(cmd[2]), cmd[3]);
        else
          updateValue(cmd[1], cmd[2]);
      }
      else if(cmd[0] == "MERGE"){
        mergeCell(stoi(cmd[1]),stoi(cmd[2]),stoi(cmd[3]),stoi(cmd[4]));
      }
      else if(cmd[0] == "UNMERGE"){
        unmergeCell(stoi(cmd[1]),stoi(cmd[2]));
      }
      else if(cmd[0] == "PRINT"){
        answer.push_back(printCell(stoi(cmd[1]),stoi(cmd[2])));
      }
    }
    return answer;
}