forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path6.cpp
More file actions
92 lines (89 loc) ยท 3.67 KB
/
6.cpp
File metadata and controls
92 lines (89 loc) ยท 3.67 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
// ํ์ฌ ์ค์น๋ ๊ตฌ์กฐ๋ฌผ์ด '๊ฐ๋ฅํ' ๊ตฌ์กฐ๋ฌผ์ธ์ง ํ์ธํ๋ ํจ์
bool possible(vector<vector<int> > answer) {
for (int i = 0; i < answer.size(); i++) {
int x = answer[i][0];
int y = answer[i][1];
int stuff = answer[i][2];
if (stuff == 0) { // ์ค์น๋ ๊ฒ์ด '๊ธฐ๋ฅ'์ธ ๊ฒฝ์ฐ
bool check = false;
// '๋ฐ๋ฅ ์'๋ผ๋ฉด ์ ์
if (y == 0) check = true;
// '๋ณด์ ํ ์ชฝ ๋ ๋ถ๋ถ ์' ํน์ '๋ค๋ฅธ ๊ธฐ๋ฅ ์'๋ผ๋ฉด ์ ์
for (int j = 0; j < answer.size(); j++) {
if (x - 1 == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
check = true;
}
if (x == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
check = true;
}
if (x == answer[j][0] && y - 1 == answer[j][1] && 0 == answer[j][2]) {
check = true;
}
}
if (!check) return false; // ์๋๋ผ๋ฉด ๊ฑฐ์ง(False) ๋ฐํ
}
else if (stuff == 1) { // ์ค์น๋ ๊ฒ์ด '๋ณด'์ธ ๊ฒฝ์ฐ
bool check = false;
bool left = false;
bool right = false;
// 'ํ์ชฝ ๋๋ถ๋ถ์ด ๊ธฐ๋ฅ ์' ํน์ '์์ชฝ ๋๋ถ๋ถ์ด ๋ค๋ฅธ ๋ณด์ ๋์์ ์ฐ๊ฒฐ'์ด๋ผ๋ฉด ์ ์
for (int j = 0; j < answer.size(); j++) {
if (x == answer[j][0] && y - 1 == answer[j][1] && 0 == answer[j][2]) {
check = true;
}
if (x + 1 == answer[j][0] && y - 1 == answer[j][1] && 0 == answer[j][2]) {
check = true;
}
if (x - 1 == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
left = true;
}
if (x + 1 == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
right = true;
}
}
if (left && right) check = true;
if (!check) return false; // ์๋๋ผ๋ฉด ๊ฑฐ์ง(False) ๋ฐํ
}
}
return true;
}
vector<vector<int> > solution(int n, vector<vector<int> > build_frame) {
vector<vector<int> > answer;
// ์์
(frame)์ ๊ฐ์๋ ์ต๋ 1,000๊ฐ
for (int i = 0; i < build_frame.size(); i++) {
int x = build_frame[i][0];
int y = build_frame[i][1];
int stuff = build_frame[i][2];
int operate = build_frame[i][3];
if (operate == 0) { // ์ญ์ ํ๋ ๊ฒฝ์ฐ
// ์ผ๋จ ์ญ์ ๋ฅผ ํด ๋ณธ ๋ค์
int index = 0;
for (int j = 0; j < answer.size(); j++) {
if (x == answer[j][0] && y == answer[j][1] && stuff == answer[j][2]) {
index = j;
}
}
vector<int> erased = answer[index];
answer.erase(answer.begin() + index);
if (!possible(answer)) { // ๊ฐ๋ฅํ ๊ตฌ์กฐ๋ฌผ์ธ์ง ํ์ธ
answer.push_back(erased); // ๊ฐ๋ฅํ ๊ตฌ์กฐ๋ฌผ์ด ์๋๋ผ๋ฉด ๋ค์ ์ค์น
}
}
if (operate == 1) { // ์ค์นํ๋ ๊ฒฝ์ฐ
// ์ผ๋จ ์ค์น๋ฅผ ํด ๋ณธ ๋ค์
vector<int> inserted;
inserted.push_back(x);
inserted.push_back(y);
inserted.push_back(stuff);
answer.push_back(inserted);
if (!possible(answer)) { // ๊ฐ๋ฅํ ๊ตฌ์กฐ๋ฌผ์ธ์ง ํ์ธ
answer.pop_back(); // ๊ฐ๋ฅํ ๊ตฌ์กฐ๋ฌผ์ด ์๋๋ผ๋ฉด ๋ค์ ์ ๊ฑฐ
}
}
}
// ์ ๋ ฌ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ฐํ
sort(answer.begin(), answer.end());
return answer;
}