이번문제는 시뮬레이션 문제이다.
난이도가 상당했지만, 구현자체는 어렵지 않았던 문제
이 문제의 핵심은 두가지이다.
- 설치할때 설치가 가능한가?
- 삭제할때 삭제가 가능한가?
처음에 이 문제를 접근할때, struct로 보와 기둥을 만들어서 포인터로 연결해서 따져야하나? 싶기도 했는데, 이건 너무 복잡해서 포기
결국 그냥 문제에서 주어진 그림대로, 설치할때 설치조건이 맞는지 확인, 삭제할때 삭제 조건에 맞는지 확인 하기 위해서
처음에 이런식으로 풀까?
생각을 했다.
그런데 이렇게 구현은 했는데, 일단 설치를 하는건 조건에 따라, 기둥이면 밑에가 true인지 혹은 보면, 보가 설치될수있는 조건이 true인지 확인하면 됬었는데,
삭제가 문제였다. 삭제를 할때 도대체 어떤식으로 접근을 해야하나, BackTracking처럼 삭제를 할때 근방을 돌면서 삭제조건을 확인해야하나? 싶었는데 이것도 너무 복잡할것 같아서, 답을 보고 풀었다.
기본아이디어
위에서 생각했던것 처럼 bool형 map을 만드는건 맞다. 그러나, 핵심은 기둥과 보를 나누는것이다.
마치 이것처럼 말이다.
그래서 기둥을 세울때는 기둥을 세울수 있는 조건인지 확인후에 column에다가 true를 놓고,
바를 세울때는 바를 세울수 있는지 조건인지 확인 후에 bar에다가 true를 갱신하였다.
그래서 코드를 보면
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
for(int i=0;i<build_frame.size();i++){
int x = build_frame[i][0];
int y = build_frame[i][1];
int type = build_frame[i][2];
int cmd = build_frame[i][3];우선 for문을 돌면서, x,y좌표와 type과 삭제,설치 명령을 가져온다.
if(type==0){
...
}
if(type==1){
...
}그래서 보와 기둥일때를 나눠서 로직을 짠다.
if 기둥일때
if(type==0){
if(cmd==1 && checkcolumn(x,y)){
cout<<"make column"<<x<<" "<<y<<"\n";
column[x][y]=true;
}
if(cmd==0){
...
}기둥일때 cmd가 1 즉 설치일경우에는 설치해도 좋은 조건인지 checkcolumn메서드를 통해 확인한다.
만약에 true가 반환되었다면 column[x][y] 좌표를 true로 만든다.
checkcolumn
bool checkcolumn(int x, int y){
//1번, 바닥인경우
if(y==0) return true;
//2번 아래에 기둥이 있는경우
if(column[x][y-1]) return true;
//3번 왼쪽에 보가 있는경우
if(x-1>=0 && bar[x-1][y]) return true;
//4번 오른쪽에 보가 있는경우
if(bar[x][y]) return true;
return false;
}기둥을 세울수있는 조건은 4가지이다.
바닥인경우 true 아래에 기둥이있는꼉우, 왼쪽에 보가 있는경우, 오른쪽에 보가있는경우를 확인해서 return true를 해주고
4가지 경우에 포함이 안되면 return false를 해준다.
참고로 x-1>=0을 꼭 조건을 달아서 x==0일때 음수가되면 coredump오류가 발생하니까 꼭 적어주자.
if 보일때
if(type==1){
if(cmd==1 && checkbar(x,y)){
cout<<"make bar"<<x<<" "<<y<<"\n";
bar[x][y]=true;
}
if(cmd==0){
...
}
}보일때도 마찬가지이다.
checkbar
bool checkbar(int x, int y ){
//1번 기둥위치에서 오른쪽으로 ㅣ -> ㅡ
if(column[x][y-1]) return true;
//2번 기역자 ㄱ
if(x+1<=100 && column[x+1][y-1]) return true;
//3번 ㅡㅡㅡ 보보보
if(x-1>=0 && bar[x-1][y] && x+1<=100 && bar[x+1][y]){ cout<<"hei";return true;}
return false;
}보를 세울수있는 경우는 3가지이다.
첫번쨰로 기둥위치에서 오른쪽으로 세우는경우
두번째로 기역자로 기둥위치에서 왼쪽으로 세우는경우
마지막으로 보보보인경우
각 조건에 따라서 column,bar의 bool형 배열에서 확인하면된다.
기둥삭제
삭제가 조금 까다로운데
if(type==0){
if(cmd==1 && checkcolumn(x,y)){
cout<<"make column"<<x<<" "<<y<<"\n";
column[x][y]=true;
}
if(cmd==0){
column[x][y]=false;
//if문으로 기둥을 지웠을때 확인해야하는요소
if(y+1<=100 && column[x][y+1] && !checkcolumn(x,y+1)){
cout<<"option 1"<<" ";
column[x][y]=true;
}else if(y+1<=100 && bar[x][y+1] && !checkbar(x,y+1)){
cout<<"option 2"<<" ";
column[x][y]=true;
}else if(x-1>=0 && y+1<=100 && bar[x-1][y+1] && !checkbar(x-1,y+1)){
cout<<"option 3"<<" ";
column[x][y]=true;
}
}
}cmd가 0인과정에서
일단 column[x][y] 삭제하고자하는 기둥을 false로 빼준다.
그다음에, 삭제하고 나서 지웠을때 확인 해야하는 요소들을 검사한다.
이게 무슨말이냐면, 기둥을 내가 일단 뺏다고 치자.
그러면, 뺀 기둥위에 있는 기둥은 검사를 해야한다.
그다음에 뺀 기둥 오른쪽으로 보가 있으면 검사를 해야한다.
그다음에 뺀 기둥 왼쪽에 보가 있으면 검사를 해야한다.
그래서 만약에 검사를 해야하는 위치에 column[x][y+1]등으로 true라서 기둥이 있으면, 이 x,y+1위치에있는 기둥이 세울수 있나 checkcolumn,checkbar로 확인을해야한다. false가 return되면, 내가 기둥을 빼버리면, 조건에 만족하지 못한다는 말이니까,
뺀 기둥을 다시 true로 반환한다.
보삭제
if(type==1){
if(cmd==1 && checkbar(x,y)){
cout<<"make bar"<<x<<" "<<y<<"\n";
bar[x][y]=true;
}
if(cmd==0){
bar[x][y]=false;
//if문으로 보을 지웠을때 확인해야하는요소
if(column[x][y] && !checkcolumn(x,y)){
cout<<"option 1"<<" ";
bar[x][y]=true;
}else if(x+1<=100 && column[x+1][y] && !checkcolumn(x+1,y)){
cout<<"option 2"<<" ";
bar[x][y]=true;
}else if(x-1>=0 && bar[x-1][y] && !checkbar(x-1,y)){
cout<<"option 3"<<" ";
bar[x][y]=true;
}else if(x+1<=100 && bar[x+1][y] && !checkbar(x+1,y)){
cout<<"option 4"<<" ";
bar[x][y]=true;
}
if(bar[x][y]==false) cout<<"bar"<<x<<" "<<y<<"delete"<<"\n";
}보삭제는 4가지 조건을 확인하면된다.
보 왼쪽에 기둥이 있거나, 보 오른쪽에 기둥이 있거나, 혹은 보보보에서 가운데 보가 빠져버리면, 왼쪽보와 오른쪽보가 남아 있을 수 있는지 checkcolumn, checkbar메서드로 확인하면 된다.
그다음에 각 map을 돌면서 기둥부터 넣어주면된다.
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(column[i][j]){
answer.push_back({i,j,0});
}
if(bar[i][j]){
answer.push_back({i,j,1});
}
}
}전체코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool column[101][101];
bool bar[101][101];
bool checkcolumn(int x, int y){
//1번, 바닥인경우
if(y==0) return true;
//2번 아래에 기둥이 있는경우
if(column[x][y-1]) return true;
//3번 왼쪽에 보가 있는경우
if(x-1>=0 && bar[x-1][y]) return true;
//4번 오른쪽에 보가 있는경우
if(bar[x][y]) return true;
return false;
}
bool checkbar(int x, int y ){
//1번 기둥위치에서 오른쪽으로 ㅣ -> ㅡ
if(column[x][y-1]) return true;
//2번 기역자 ㄱ
if(x+1<=100 && column[x+1][y-1]) return true;
//3번 ㅡㅡㅡ 보보보
if(x-1>=0 && bar[x-1][y] && x+1<=100 && bar[x+1][y]){ cout<<"hei";return true;}
return false;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
for(int i=0;i<build_frame.size();i++){
int x = build_frame[i][0];
int y = build_frame[i][1];
int type = build_frame[i][2];
int cmd = build_frame[i][3];
if(type==0){
if(cmd==1 && checkcolumn(x,y)){
cout<<"make column"<<x<<" "<<y<<"\n";
column[x][y]=true;
}
if(cmd==0){
column[x][y]=false;
//if문으로 기둥을 지웠을때 확인해야하는요소
if(y+1<=100 && column[x][y+1] && !checkcolumn(x,y+1)){
cout<<"option 1"<<" ";
column[x][y]=true;
}else if(y+1<=100 && bar[x][y+1] && !checkbar(x,y+1)){
cout<<"option 2"<<" ";
column[x][y]=true;
}else if(x-1>=0 && y+1<=100 && bar[x-1][y+1] && !checkbar(x-1,y+1)){
cout<<"option 3"<<" ";
column[x][y]=true;
}
}
}
if(type==1){
if(cmd==1 && checkbar(x,y)){
cout<<"make bar"<<x<<" "<<y<<"\n";
bar[x][y]=true;
}
if(cmd==0){
bar[x][y]=false;
//if문으로 보을 지웠을때 확인해야하는요소
if(column[x][y] && !checkcolumn(x,y)){
cout<<"option 1"<<" ";
bar[x][y]=true;
}else if(x+1<=100 && column[x+1][y] && !checkcolumn(x+1,y)){
cout<<"option 2"<<" ";
bar[x][y]=true;
}else if(x-1>=0 && bar[x-1][y] && !checkbar(x-1,y)){
cout<<"option 3"<<" ";
bar[x][y]=true;
}else if(x+1<=100 && bar[x+1][y] && !checkbar(x+1,y)){
cout<<"option 4"<<" ";
bar[x][y]=true;
}
if(bar[x][y]==false) cout<<"bar"<<x<<" "<<y<<"delete"<<"\n";
}
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(column[i][j]){
answer.push_back({i,j,0});
}
if(bar[i][j]){
answer.push_back({i,j,1});
}
}
}
return answer;
}