https://programmers.co.kr/learn/courses/30/lessons/60061
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
<풀이>
1. 입력으로 주어지는 명령어를 해독하여 기둥과 보를 설치하거나 지운다.
2. 모든 명령어를 수행하고 결과를 저장한다.
<해법>
1. 기둥과 보를 설치하거나 지우는 방법.
=>
(1) 기둥과 보를 설치하는 방법
설치하는 방법은 문제에 나온 조건에 맞게 정확히 구현합니다.
(2) 기둥과 보를 지우는 방법
지우는 방법은 먼저 그 건축물을 map에서 지웁니다. 지운 후 건축물과 관련이 있는 다른 건축물이 설치될 수 있는 지를 확인합니다. 설치될 수 있는지를 확인할 때, 미리 만들어 놓은 설치 함수들을 사용하면 편리합니다.
|
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
char map[2][102][102];
bool canBuildPillar(int n, int x, int y) {
//기둥이 바닥 위에 있을 경우
if (x == 0) {
return true;
}
//기둥이 다른 기둥 위에 있을 경우
if (x - 1 >= 0 && map[0][x - 1][y] == 'p') {
return true;
}
//기둥이 왼쪽 보의 끝 위에 있을 경우
if (y - 1 >= 0 && map[1][x][y - 1] == 'b') {
return true;
}
//기둥이 오른쪽 보의 끝 위에 있을 경우
if (map[1][x][y] == 'b') {
return true;
}
return false;
}
bool canBuildBo(int n, int x, int y) {
//보의 왼쪽 끝 부분이 기둥 위에있을 경우
if (x - 1 >= 0 && map[0][x - 1][y] == 'p') {
return true;
}
//보의 오른쪽 끝 부분이 기둥 위에있을 경우
if (x - 1 >= 0 && y + 1 <= n && map[0][x - 1][y + 1] == 'p') {
return true;
}
//보의 양쪽 끝이 다른 보와 동시에 연결되어 있을 경우
if (y - 1 >= 0 && y + 1 <= n && map[1][x][y - 1] == 'b' && map[1][x][y + 1] == 'b') {
return true;
}
return false;
}
bool canDeletePillar(int n, int x, int y) {
//기둥을 지운다
map[0][x][y] = '0';
//기둥 위에 있는 다른 기둥이 지을 수 있는지 확인
if (x + 1 <= n && map[0][x + 1][y] == 'p') {
if (!canBuildPillar(n, x + 1, y)) {
return false;
}
}
//기둥 위에 오른쪽으로 걸쳐있는 보가 지을 수 있는지 확인
if (x + 1 <= n && map[1][x + 1][y] == 'b') {
if (!canBuildBo(n, x + 1, y)) {
return false;
}
}
//기둥 위에 왼쪽으로 걸쳐있는 보가 지을 수 있는지 확인
if (x + 1 <= n && y - 1 >= 0 && map[1][x + 1][y - 1] == 'b') {
if (!canBuildBo(n, x + 1, y - 1)) {
return false;
}
}
return true;
}
bool canDeleteBo(int n, int x, int y) {
//보를 지운다
map[1][x][y] = '0';
//보 오른쪽 끝 위에 있는 기둥이 지을 수 있는지 확인
if (y + 1 <= n && map[0][x][y + 1] == 'p') {
if (!canBuildPillar(n, x, y + 1)) {
return false;
}
}
//보 왼쪽 끝 위에 있는 기둥이 지을 수 있는지 확인
if (map[0][x][y] == 'p') {
if (!canBuildPillar(n, x, y)) {
return false;
}
}
//보 오른쪽에 있는 다른 보가 지을 수 있는지 확인
if (y + 1 <= n && map[1][x][y + 1] == 'b') {
if (!canBuildBo(n, x, y + 1)) {
return false;
}
}
//보 왼쪽에 있는 다른 보가 지을 수 있는지 확인
if (y - 1 >= 0 && map[1][x][y - 1] == 'b') {
if (!canBuildBo(n, x, y - 1)) {
return false;
}
}
return true;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
memset(map, '0', sizeof(map));
for (int i = 0; i < build_frame.size(); i++) {
int y = build_frame[i][0];
int x = build_frame[i][1];
int shape = build_frame[i][2];
int install = build_frame[i][3];
//지우는 경우
if (install == 0) {
//기둥을 지우는 경우
if (shape == 0) {
//지울 수 있는지 확인
if (!canDeletePillar(n, x, y)) {
map[0][x][y] = 'p';
}
}
//보를 지우는 경우
else {
if (!canDeleteBo(n, x, y)) {
map[1][x][y] = 'b';
}
}
}
//짓는 경우
else {
//기둥을 짓는 경우
if (shape == 0) {
//지을 수 있는지 확인
if (canBuildPillar(n, x, y)) {
map[0][x][y] = 'p';
}
}
//보를 짓는 경우
else {
if (canBuildBo(n, x, y)) {
map[1][x][y] = 'b';
}
}
}
}
//결과 저장
for (int j = 0; j <= n; j++) {
for (int i = 0; i <= n; i++) {
for (int k = 0; k < 2; k++) {
if (map[k][i][j] != '0') {
answer.push_back({ j,i,k });
}
}
}
}
return answer;
}
|
구현에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글
| [C++] 프로그래머스 - 크레인 인형뽑기 게임 (0) | 2020.05.07 |
|---|---|
| [C++] 프로그래머스 - 외벽 점검 (0) | 2020.05.07 |
| [C++] 프로그래머스 - 블록 이동하기 (0) | 2020.05.07 |
| [C++] 프로그래머스 - 자물쇠와 열쇠 (0) | 2020.05.07 |
| [C++] 프로그래머스 - 괄호 변환 (0) | 2020.05.04 |