[2020 KAKAO BLIND RECRUITMENT] 기둥과 보 설치
[링크] https://programmers.co.kr/learn/courses/30/lessons/60061
💎 문제 조건과 설명
문제 조건과 설명은 위의 링크를 참조 부탁드립니다.
🚀 생각한 아이디어
구현 문제의 경우, 주어진 대로 구현을 차근차근 하면 되는데 주어진 조건을 하나도 빠짐없이, 그리고 오류 없이 구현해야 되어서 주의가 많이 필요한 문제였습니다.
먼저 기둥의 조건은 다음과 같습니다.
바닥 위에 있어야 한다.
- 혹은, 보의 한쪽 끝 부분 위에 있어야 한다.
- 혹은, 다른 기둥 위에 있어야 한다.
보의 조건은 다음과 같습니다.
- 한쪽 끝 부분이 기둥 위에 있어야 한다.
- 혹은, 양쪽 끝 부분에 다른 보가 동시에 연결되어 있어야 한다.
구조물을 설치 혹은 삭제할 때에도 반드시 위 조건은 항상 만족해야 합니다. 또한 보는 좌표에서 설치할 때 오른쪽 방향으로 설치됨을 나타내고, 기둥은 위쪽 방향으로 설치됨을 나타냅니다.
그림으로 예시를 살펴보도록 하겠습니다.
구조물 설치 혹은 삭제의 명령은 (x,y,a,b)로 나타나며 (x,y) 위치에 a(기둥-0 혹은 보-1)를 b(삭제-0 혹은 설치-1) 하라는 의미입니다.
[예시 1] (0,0,0,1), (0,1,1,1), (3,0,0,1), (2,1,1,1), (1,1,1,1) 까지 수행 후 아래와 같은 구조물 생성
[예시 2] 혹은 아래와 같은 구조물도 생성 가능합니다.
그런데 구조물을 설치할 때, 기둥 및 보의 조건을 만족하면 되므로 아래와 같은 구조물도 가능합니다.
각 좌표에서 보는 오른쪽 방향으로 설치되고, 기둥은 위쪽 방향으로 설치되는 것이라고 문제 조건에 나와 있으니, 같은 (x, y) 좌표에서 조건만 만족한다면 기둥과 보 모두 설치가 가능할 수 있습니다.
그래서 코드 작성을 할 때 [y][x] 좌표에 기둥 혹은 보라는 표시를 할 텐데, 같은 좌표에 기둥이나 보 모두 올 수가 있으므로 3차원 배열로 [y][x][0] 혹은 [y][x][1]로 표현해야 겠다는 생각을 하였습니다.
구조물을 설치하고, 조건에 맞는지 판단한 뒤, 맞지 않으면 설치하지 않고 넘어가는 식으로 코드를 작성했습니다.
삭제의 경우 일단 삭제를 해 보고, 조건에 맞는지 판단한 뒤, 맞지 않으면 다시 원상복구 해 놓는 식입니다.
- 소스코드
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define pb push_back
#define pillar 0
#define beam 1
#define setup 1
#define INF 1000000
using namespace std;
int arr[110][110][2]; // 격자판
bool check(int n, int y, int x) {
// 기둥 확인
if (arr[y][x][pillar] == setup) {
// 내 아래에 기둥이 있거나, 한 쪽에 보가 있을 경우 기둥 유효함
if (y == 0 || arr[y - 1][x][pillar] == 1 || arr[y][x][beam] == 1 ||
(x > 0 && arr[y][x - 1][beam] == 1)) {
return true;
}
else
return false;
}
// 보 확인
if (arr[y][x][beam] == setup) {
// 보 설치 시 양쪽 중 하나 밑에 기둥이 있으면 유효함
// 혹은 양 옆에 보가 있어도 유효함
if ((y > 0 && arr[y - 1][x][pillar] == 1) || (y > 0 && arr[y - 1][x + 1][pillar] == 1)
|| (x > 0 && x < n && arr[y][x - 1][beam] == 1 && arr[y][x + 1][beam] == 1)) {
return true;
}
else
return false;
}
return true;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
vector<int> temp;
// 처음에 격자판을 모두 -로 초기화
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
arr[i][j][0] = -INF;
arr[i][j][1] = -INF;
}
}
for (int i = 0; i < build_frame.size(); i++) {
int x = build_frame[i][0];
int y = build_frame[i][1];
int category = build_frame[i][2];
int crtORdel = build_frame[i][3];
// 설치
if (crtORdel == 1) {
// 기둥일 경우
if (category == pillar) {
arr[y][x][pillar] = setup; // 일단 설치 후 검증
if (check(n, y, x) == false) {
arr[y][x][pillar] = -INF; // 조건에 어긋나면 설치 취소
}
}
// 보일 경우
else {
arr[y][x][beam] = setup; // 일단 설치 후 검증
if (check(n, y, x) == false) {
arr[y][x][beam] = -INF; // 조건에 어긋나면 설치 취소
}
}
}
// 삭제
else {
// 기둥일 경우
if (category == pillar) {
if (arr[y][x][pillar] == setup) {
arr[y][x][pillar] = -INF; // 일단 삭제 후 검증
// 기둥이 삭제될 경우 0. 그 자리 검사
// 1. 그 위에 있던 기둥의 유효성 검증
// 2. 그 기둥 위에 서있을 수 있었던 보의 위치 검사
if (!(check(n, y, x) && check(n, y + 1, x) && check(n, y + 1, x - 1))) {
arr[y][x][pillar] = setup;
}
}
}
// 보일 경우
else {
if (arr[y][x][beam] == setup) {
arr[y][x][beam] = -INF; // 일단 삭제 후 검증
// 보가 삭제될 경우
// 1. 그 좌표 뿐만 아니라 그 옆에 있던 보들도 유효성 검사
if (!(check(n, y, x) && check(n, y, x - 1) && check(n, y, x + 1))) {
arr[y][x][beam] = setup;
}
}
}
}
}
vector<int> answer_temp;
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
if (arr[i][j][pillar] == setup) {
answer_temp.pb(j);
answer_temp.pb(i);
answer_temp.pb(pillar);
answer.pb(answer_temp);
answer_temp.clear();
}
if (arr[i][j][beam] == setup) {
answer_temp.pb(j);
answer_temp.pb(i);
answer_temp.pb(beam);
answer.pb(answer_temp);
answer_temp.clear();
}
}
}
sort(answer.begin(), answer.end());
return answer;
}