[C++로 풀이] 기둥과 보 설치⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 기둥과 보 설치
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이 ⭕
추가
- “기둥”을 추가할 때
- 기둥의 3 가지 조건 중 하나라도 만족하는지 추가하려는 기둥을 검사 하고 기둥을 추가한다.
- “보”를 추가할 때
- 보의 2 가지 조건 중 하나라도 만족하는지 추가하려는 보를 검사 하고 기둥을 추가한다.
삭제
이 기둥 혹은 보를 먼저 삭제시키고, 삭제시키고난 후에 주변 기둥들과 보들이 조건을 위배하게 되진 않았는지를 검사한다. 하나라도 위배가 되면 이 기둥 혹은 보를 삭제하면 모순이 생긴다는 것임으로 삭제를 다시 취소하면 된다!
- “기둥”을 삭제할 때
- 기둥의 3 가지 조건 중 하나라도 만족하는지 삭제한 기둥의 위 쪽 기둥을 검사 하고 모두 만족하지 못하다면 이 기둥을 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
- 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 기둥이 왼 쪽에 오는 위 쪽 보를 검사 하고 모두 만족하지 못하다면 이 기둥을 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
- 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 기둥이 오른 쪽에 오는 위 쪽 보를 검사 하고 모두 만족하지 못하다면 이 기둥을 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
- “보”를 삭제할 때
- 기둥의 3 가지 조건 중 하나라도 만족하는지 삭제한 보의 왼 쪽 위의 기둥을 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
- 기둥의 3 가지 조건 중 하나라도 만족하는지 삭제한 보의 오른 쪽 위의 기둥을 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
- 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 보의 왼쪽에 연결된 보를 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
- 보의 2 가지 조건 중 하나라도 만족하는지 삭제한 보의 오른쪽에 연결된 보를 검사 하고 모두 만족하지 못하다면 이 보를 삭제하면 모순이 생기는 것이므로 삭제를 취소한다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool board[101][101][2]; // [x][y][0] 기둥 [x][y][1] 보
int num = 0; // 벽면 사이즈
bool IsColumnOK(int x, int y) {
bool cond1 = y == 0;
bool cond2 = board[x][y][1] || (x - 1 >= 0 && board[x - 1][y][1]);
bool cond3 = y - 1 >= 0 && board[x][y - 1][0];
return cond1 || cond2 || cond3;
}
bool IsPaperOK(int x, int y) {
bool cond1 = (board[x][y - 1][0] || (x + 1 <= num && board[x + 1][y - 1][0])); // y - 1 생략
bool cond2 = (x - 1 >= 0 && board[x - 1][y][1]) && (x + 1 <= num && board[x + 1][y][1]);
return cond1 || cond2;
}
bool compare(vector<int> a, vector<int> b) {
if (a[0] == b[0] && a[1] == b[1])
return a[2] < b[2];
if (a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
num = n;
for (int i = 0; i < build_frame.size(); ++i) {
int x = build_frame[i][0];
int y = build_frame[i][1];
if (build_frame[i][3] == 0) {
if (build_frame[i][2] == 0) { // 기둥 삭제
if (!board[x][y][0])
continue;
board[x][y][0] = false; // 삭제
if (y + 1 <= n && board[x][y + 1][0] && !IsColumnOK(x, y + 1)) {
board[x][y][0] = true; // 삭제취소
continue;
}
if (y + 1 <= n && board[x][y + 1][1] && !IsPaperOK(x, y + 1)) {
board[x][y][0] = true; // 삭제취소
continue;
}
if (x - 1 >= 0 && y + 1 <= n && board[x - 1][y + 1][1] && !IsPaperOK(x - 1, y + 1)) {
board[x][y][0] = true; // 삭제취소
continue;
}
}
else { // 보 삭제
if (!board[x][y][1])
continue;
board[x][y][1] = false; // 삭제
if (board[x][y][0] && !IsColumnOK(x, y)) {
board[x][y][1] = true; // 삭제취소
continue;
}
if (x + 1 <= n && board[x + 1][y][0] && !IsColumnOK(x + 1, y)) {
board[x][y][1] = true; // 삭제취소
continue;
}
if (x - 1 >= 0 && board[x - 1][y][1] && !IsPaperOK(x - 1, y)) {
board[x][y][1] = true; // 삭제취소
continue;
}
if (x + 1 <= n && board[x + 1][y][1] && !IsPaperOK(x + 1, y)) {
board[x][y][1] = true; // 삭제취소
continue;
}
}
}
else {
if (build_frame[i][2] == 0) { // 기둥 추가
if (IsColumnOK(x, y))
board[x][y][0] = true;
}
else { // 보 추가
if (IsPaperOK(x, y))
board[x][y][1] = true;
}
}
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
if (board[i][j][0]) {
vector<int> v(3);
v[0] = i;
v[1] = j;
v[2] = 0;
answer.push_back(v);
}
if (board[i][j][1]) {
vector<int> v(3);
v[0] = i;
v[1] = j;
v[2] = 1;
answer.push_back(v);
}
}
}
sort(answer.begin(), answer.end(), compare);
return answer;
}
✈ 조건을 검사하는 함수
매우매우매우 중요한 부분인데, 이 문제는 num을 포함한다! 즉 이 벽면의 사이즈가 5 x 5 라면 0,1,2,3,4,5 이렇게 5까지 좌표에 포함된다는 것이다!!!!! 이에 대해 생각을 못하고 평소처럼 범위를 벗어나지 않는 조건으로 x + 1 < num 이런 식으로 잡는 바람에 틀렸었는데 원인 찾느라 애먹었다.. 😭 x + 1 <= num 이라고 해야 한다.
따라서 배열은 (n + 1) x (n + 1) 크기로 선언이 되야 한다. 벽면의 최대 사이즈는 100 이라고 문제에서 주어져서 나는 그냥 bool board[101][101][2] 101 x 101 크기로 선언했다. [x][y][0] 은 기둥 자리이고, [x][y][1]은 보 자리이다. 이 board에 기둥 혹은 보가 현재 벽면에 추가되어 있는 상태라면, 즉 존재하는 상태라면 해당 자리가 true 인 상태이다. 예를들어 [x][y][0]가 true 이면 (x, y)에 기둥이 현재 존재한다는 뜻이다. 삭제 또한 이 값을 false 로 만들어주는 식으로 처리할 것이다.
bool board[101][101][2]; // [x][y][0] 기둥 [x][y][1] 보
int num = 0;
/* (x, y)에 위치한 기둥의 조건을 검사하는 함수 */
bool IsColumnOK(int x, int y) {
// 1. 바닥 위에 있거나
bool cond1 = y == 0;
// 2. 보의 한쪽 끝 부분에 있거나
// (기둥이 보의 왼쪽에 있다면 이 보는 board[x][y][1])
// (기둥이 보의 오른쪽에 있다면 이 보는 board[x - 1][y][1])
bool cond2 = board[x][y][1] || (x - 1 >= 0 && board[x - 1][y][1]);
// 3. 다른 기둥 위에 있어야 한다. (즉, 아래쪽에 기둥이 있어야 한다.)
bool cond3 = y - 1 >= 0 && board[x][y - 1][0];
return cond1 || cond2 || cond3; // 위 3 가지 조건 중 하나만이라도 만족하면 된다.
}
/* (x, y)에 위치한 보의 조건을 검사하는 함수 */
bool IsPaperOK(int x, int y) {
// 1. 한쪽 끝 부분이 기둥위에 있거나
// (보의 왼쪽 아래에 기둥이 있다면 이 기둥은 board[x][y - 1][0])
// (보의 오른쪽 아래에 기둥이 있다면 이 기둥은 board[x + 1][y - 1][0]))
// 문제에서 바닥에 보를 설치하는 경우는 없다고 주어졌기 때문에 y - 1 >= 0 조건은 따로 두지 않았다.
bool cond1 = (board[x][y - 1][0] || (x + 1 <= num && board[x + 1][y - 1][0]));
// 2. 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.
// (이 보의 왼쪽 보와도, 오른쪽 보와도 동시에 연결되어 있어야 한다.)
bool cond2 = (x - 1 >= 0 && board[x - 1][y][1]) && (x + 1 <= num && board[x + 1][y][1]);
return cond1 || cond2; // 위 2 가지 조건 중 하나만이라도 만족하면 된다.
}
✈ 기둥 삭제
int x = build_frame[i][0];
int y = build_frame[i][1];
if (build_frame[i][3] == 0) { // 삭제
if (build_frame[i][2] == 0) { // 기둥 삭제
if (!board[x][y][0]) // 삭제하려는 기둥이 벽면에 존재하지 않는다면 넘어가기
continue;
board[x][y][0] = false; // 삭제해보고
if (y + 1 <= n && board[x][y + 1][0] && !IsColumnOK(x, y + 1)) { // 삭제한 기둥의 위 쪽 기둥에 모순이 생기는지 검사
board[x][y][0] = true; // 모순이 생긴다면 삭제 취소
continue;
}
if (y + 1 <= n && board[x][y + 1][1] && !IsPaperOK(x, y + 1)) { // 삭제한 기둥이 왼 쪽에 오는 위 쪽 보가 모순이 생기는지 검사
board[x][y][0] = true; // 모순이 생긴다면 삭제 취소
continue;
}
if (x - 1 >= 0 && y + 1 <= n && board[x - 1][y + 1][1] && !IsPaperOK(x - 1, y + 1)) { // 삭제한 기둥이 오른 쪽에 오는 위 쪽 보가 모순이 생기는지 검사
board[x][y][0] = true; // 모순이 생긴다면 삭제 취소
continue;
}
}
✈ 보 삭제
int x = build_frame[i][0];
int y = build_frame[i][1];
if (build_frame[i][3] == 0) { // 삭제
if (build_frame[i][2] == 1) { // 보 삭제
if (!board[x][y][1]) // 삭제하려는 보가 벽면에 존재하지 않는다면 넘어가기
continue;
board[x][y][1] = false; // 삭제해보고
if (board[x][y][0] && !IsColumnOK(x, y)) { // 삭제한 보의 왼 쪽 위의 기둥에 모순이 생기는지 검사
board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
continue;
}
if (x + 1 <= n && board[x + 1][y][0] && !IsColumnOK(x + 1, y)) { // 삭제한 보의 오른 쪽 위의 기둥에 모순이 생기는지 검사
board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
continue;
}
if (x - 1 >= 0 && board[x - 1][y][1] && !IsPaperOK(x - 1, y)) { // 삭제한 보의 왼쪽에 연결된 보에 모순이 생기는지 검사
board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
continue;
}
if (x + 1 <= n && board[x + 1][y][1] && !IsPaperOK(x + 1, y)) { // 삭제한 보의 오른쪽에 연결된 보에 모순이 생기는지 검사
board[x][y][1] = true; // 모순이 생긴다면 삭제 취소
continue;
}
}
✈ 기둥, 보 추가
else {
if (build_frame[i][2] == 0) { // 기둥 추가
if (IsColumnOK(x, y)) // 추가하려는 기둥 검사
board[x][y][0] = true; // 괜찮다면 추가 완료
}
else { // 보 추가
if (IsPaperOK(x, y)) // 추가하려는 보 검사
board[x][y][1] = true; // 괜찮다면 추가 완료
}
}
✈ answer 에 출력하기
// 0 ~ n 행, 0 ~ n 열 차례대로
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
if (board[i][j][0]) { // 기둥이라면
vector<int> v(3);
v[0] = i;
v[1] = j;
v[2] = 0;
answer.push_back(v);
}
if (board[i][j][1]) { // 보라면
vector<int> v(3);
v[0] = i;
v[1] = j;
v[2] = 1;
answer.push_back(v);
}
}
}
✈ 정렬하기
정렬 조건은 이러했다.
bool compare(vector<int> a, vector<int> b) {
if (a[0] == b[0] && a[1] == b[1])
return a[2] < b[2];
if (a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
}
//...
sort(answer.begin(), answer.end(), compare);
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기