728x90
반응형
https://www.acmicpc.net/problem/20061
20061번: 모노미노도미노 2
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행,
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ20061
//
// Created by 최화연 on 2022/04/27.
//
#include <iostream>
#include <vector>
using namespace std;
int N;
int board[10][10] = {0, };
vector<pair<int, pair<int, int>>> blocks;
int score = 0;
void put_block(int t, int r, int c) {
//1. 파란색 보드에 블록 놓기
switch (t) {
case 1:
for (int c=3; c<=8; c++) {
if (c+1 == 9 && board[r][c+1] == 0) {
board[r][9] = 1;
break;
}
if (board[r][c+1] == 0) continue;
board[r][c] = 1;
break;
}
break;
case 2:
for (int c=3; c<=8; c++) {
if (c+1 == 9 && board[r][c+1] == 0) {
board[r][9] = 1;
board[r][8] = 1;
break;
}
if (board[r][c+1] == 0) continue;
board[r][c] = 1;
board[r][c-1] = 1;
break;
}
break;
case 3:
for (int c=3; c<=8; c++) {
if (c+1 == 9 && board[r][c+1] == 0 && board[r+1][c+1] == 0) {
board[r][9] = 1;
board[r+1][9] = 1;
break;
}
if (board[r][c+1] == 0 && board[r+1][c+1] == 0) continue;
board[r][c] = 1;
board[r+1][c] = 1;
break;
}
break;
}
//2. 초록색 보드에 블록 놓기
switch (t) {
case 1:
for (int r=3; r<=8; r++) {
if (r+1 == 9 && board[r+1][c] == 0) {
board[9][c] = 1;
break;
}
if (board[r+1][c] == 0) continue;
board[r][c] = 1;
break;
}
break;
case 2:
for (int r=3; r<=8; r++) {
if (r+1 == 9 && board[r+1][c] == 0 && board[r+1][c+1] == 0) {
board[9][c] = 1;
board[9][c+1] = 1;
break;
}
if (board[r+1][c] == 0 && board[r+1][c+1] == 0) continue;
board[r][c] = 1;
board[r][c+1] = 1;
break;
}
break;
case 3:
for (int r=3; r<=8; r++) {
if (r+1 == 9 && board[r+1][c] == 0) {
board[9][c] = 1;
board[8][c] = 1;
break;
}
if (board[r+1][c] == 0) continue;
board[r][c] = 1;
board[r-1][c] = 1;
break;
}
break;
}
}
void check_green_board() {
int r=9;
while (r > 5) {
bool check = true;
for (int c=0; c<=3; c++) {
if (board[r][c] == 0) {
check = false;
break;
}
}
if (!check) {
r--;
continue;
}
score++;
for (int c=0; c<=3; c++) {
for (int rr=r; rr>=4; rr--) {
board[rr][c] = board[rr-1][c];
}
}
}
}
void check_blue_board() {
int c=9;
while (c > 5) {
bool check = true;
for (int r=0; r<=3; r++) {
if (board[r][c] == 0) {
check = false;
break;
}
}
if (!check) {
c--;
continue;
}
score++;
for (int r=0; r<=3; r++) {
for (int cc=c; cc>=4; cc--) {
board[r][cc] = board[r][cc-1];
}
}
}
}
void check_light_green_board() {
int n = 0;
for (int r=4; r<=5; r++) {
for (int c=0; c<=3; c++) {
if (board[r][c]) {
n ++;
break;
}
}
}
if (n == 0) return;
for (int c=0; c<=3; c++) {
for (int r=9; r>=4; r--) {
board[r][c] = board[r-n][c];
}
}
}
void check_light_blue_board() {
int n = 0;
for (int c=4; c<=5; c++) {
for (int r=0; r<=3; r++) {
if (board[r][c]) {
n ++;
break;
}
}
}
if (n == 0) return;
for (int r=0; r<=3; r++) {
for (int c=9; c>=4; c--) {
board[r][c] = board[r][c-n];
}
}
}
void monominodomino() {
for (int i=0; i<N; i++) {
int t = blocks[i].first;
int r = blocks[i].second.first;
int c = blocks[i].second.second;
put_block(t, r, c);
check_green_board();
check_blue_board();
check_light_green_board();
check_light_blue_board();
}
}
int get_blocks() {
int cnt = 0;
for (int r=0; r<=9; r++) {
for (int c=0; c<=9; c++) {
cnt += board[r][c];
}
}
return cnt;
}
int main(int argc, const char * argv[]) {
cin >> N;
for (int i=0; i<N; i++) {
int t, x, y;
cin >> t >> x >> y;
blocks.push_back({t, {x, y}});
}
monominodomino();
cout << score << endl;
cout << get_blocks() << endl;
return 0;
}풀이 과정
풀이 시간 1시간 20분
#include <iostream>
#include <vector>
using namespace std;
int N;
int board[10][10] = {0, };
vector<pair<int, pair<int, int>>> blocks;
int score = 0;
void put_block(int t, int r, int c) {
//1. 파란색 보드에 블록 놓기
switch (t) {
case 1:
for (int c=3; c<=8; c++) {
if (c+1 == 9 && board[r][c+1] == 0) {
board[r][9] = 1;
break;
}
if (board[r][c+1] == 0) continue;
board[r][c] = 1;
break;
}
break;
case 2:
for (int c=3; c<=8; c++) {
if (c+1 == 9 && board[r][c+1] == 0) {
board[r][9] = 1;
board[r][8] = 1;
break;
}
if (board[r][c+1] == 0) continue;
board[r][c] = 1;
board[r][c-1] = 1;
break;
}
break;
case 3:
for (int c=3; c<=8; c++) {
if (c+1 == 9 && board[r][c+1] == 0 && board[r+1][c+1] == 0) {
board[r][9] = 1;
board[r+1][9] = 1;
break;
}
if (board[r][c+1] == 0 && board[r+1][c+1] == 0) continue;
board[r][c] = 1;
board[r+1][c] = 1;
break;
}
break;
}
//2. 초록색 보드에 블록 놓기
switch (t) {
case 1:
for (int r=3; r<=8; r++) {
if (r+1 == 9 && board[r+1][c] == 0) {
board[9][c] = 1;
break;
}
if (board[r+1][c] == 0) continue;
board[r][c] = 1;
break;
}
break;
case 2:
for (int r=3; r<=8; r++) {
if (r+1 == 9 && board[r+1][c] == 0 && board[r+1][c+1] == 0) {
board[9][c] = 1;
board[9][c+1] = 1;
break;
}
if (board[r+1][c] == 0 && board[r+1][c+1] == 0) continue;
board[r][c] = 1;
board[r][c+1] = 1;
break;
}
break;
case 3:
for (int r=3; r<=8; r++) {
if (r+1 == 9 && board[r+1][c] == 0) {
board[9][c] = 1;
board[8][c] = 1;
break;
}
if (board[r+1][c] == 0) continue;
board[r][c] = 1;
board[r-1][c] = 1;
break;
}
break;
}
}
void check_green_board() {
int r=9;
while (r > 5) {
bool check = true;
for (int c=0; c<=3; c++) {
if (board[r][c] == 0) {
check = false;
break;
}
}
if (!check) {
r--;
continue;
}
score++;
for (int c=0; c<=3; c++) {
for (int rr=r; rr>=4; rr--) {
board[rr][c] = board[rr-1][c];
}
}
}
}
void check_blue_board() {
int c=9;
while (c > 5) {
bool check = true;
for (int r=0; r<=3; r++) {
if (board[r][c] == 0) {
check = false;
break;
}
}
if (!check) {
c--;
continue;
}
score++;
for (int r=0; r<=3; r++) {
for (int cc=c; cc>=4; cc--) {
board[r][cc] = board[r][cc-1];
}
}
}
}
void check_light_green_board() {
int n = 0;
for (int r=4; r<=5; r++) {
for (int c=0; c<=3; c++) {
if (board[r][c]) {
n ++;
break;
}
}
}
if (n == 0) return;
for (int c=0; c<=3; c++) {
for (int r=9; r>=4; r--) {
board[r][c] = board[r-n][c];
}
}
}
void check_light_blue_board() {
int n = 0;
for (int c=4; c<=5; c++) {
for (int r=0; r<=3; r++) {
if (board[r][c]) {
n ++;
break;
}
}
}
if (n == 0) return;
for (int r=0; r<=3; r++) {
for (int c=9; c>=4; c--) {
board[r][c] = board[r][c-n];
}
}
}
void monominodomino() {
for (int i=0; i<N; i++) {
int t = blocks[i].first;
int r = blocks[i].second.first;
int c = blocks[i].second.second;
put_block(t, r, c);
check_green_board();
check_blue_board();
check_light_green_board();
check_light_blue_board();
}
}
int get_blocks() {
int cnt = 0;
for (int r=0; r<=9; r++) {
for (int c=0; c<=9; c++) {
cnt += board[r][c];
}
}
return cnt;
}
int main(int argc, const char * argv[]) {
cin >> N;
for (int i=0; i<N; i++) {
int t, x, y;
cin >> t >> x >> y;
blocks.push_back({t, {x, y}});
}
monominodomino();
cout << score << endl;
cout << get_blocks() << endl;
return 0;
}이전 풀이
풀이 시간 1시간 57분
3개의 블록을 파란색 보드와 초록색 보드에 각각 올바른 위치에 놓고, 보드의 상태에 따라 블록들을 재정렬하는 문제이다.
다소 복잡해 보이지만, 테스크를 모듈화해서 함수 동작이 올바른지 그때그때 디버깅하면서 문제를 차근히 풀어나갔다.
이 문제에서 유의해야할 점은 다른 문제와 다르게 x가 행을 의미하고, y가 열을 의미한다는 것이다!!
늘 느끼지만 정답은 문제 설명에 있다. 문제를 정말정말 잘 읽자!!
각 예제를 테스트해볼 때 왜 문제에 주어진 그림이랑 다르게 출력이 되는지 몰랐다.. 다시 살펴보니 x와 y를 반대로 생각했던것!
따라서 입력을 받아올 때, x와 y값을 반대로 받아와서 문제를 해결할 수 있었다.
보드는 다음과 같이 구성했다.
/*
red board -> 0<=x<=3, 0<=y<=3
blue board -> 6<=x<=9, 0<=y<=3
sky blue board -> 4<=x<=5, 0<=y<=3
green board -> 0<=x<=3, 6<=y<=9
light green board -> 0<=x<=3, 4<=y<=5
*/
int board[10][10] = {0, };
모듈화는 다음과 같이 했다.
- put_block1(): type 1인 블록을 파란색 보드와 초록색 보드에 놓는 함수
- put_block2(): type 2인 블록을 파란색 보드와 초록색 보드에 놓는 함수
- put_block3(): type 3인 블록을 파란색 보드와 초록색 보드에 놓는 함수
- check_blue_board(): 파란색 블록의 열을 탐색하는 함수
- check_green_board(): 초록색 블록의 행을 탐색하는 함수
- check_sky_blue_board(): 연한 파란색 블록을 탐색하는 함수
- check_light_green_board(): 연한 초록색 블록을 탐색하는 함수
(1) put_block1()
void put_block1(int bx, int by){
//put block on blue board
for(int x=4; x<=8; x++){
if(board[by][x+1]){
board[by][x] = 1;
break;
}
//by 열이 비워져 있는 경우,
else if(x == 8){
board[by][9] = 1;
}
}
//put block on green board
for(int y=4; y<=8; y++){
if(board[y+1][bx]){
board[y][bx] = 1;
break;
}
//bx 행이 비워져 있는 경우,
else if(y == 8){
board[9][bx] = 1;
}
}
}
(2) put_block2()
void put_block2(int bx, int by){
//put block on blue board
for(int x=4; x<=8; x++){
if(board[by][x+1]){
board[by][x] = 1;
board[by][x-1] = 1;
break;
}
//by 열이 비워져 있는 경우,
else if(x == 8){
board[by][9] = 1;
board[by][8] = 1;
}
}
//put block on green board
for(int y=4; y<=8; y++){
if(board[y+1][bx] || board[y+1][bx+1]){
board[y][bx] = 1;
board[y][bx+1] = 1;
break;
}
//bx 행이 비워져 있는 경우,
else if(y == 8){
board[9][bx] = 1;
board[9][bx+1] = 1;
}
}
}
(3) put_block3()
void put_block3(int bx, int by){
//put block on blue board
for(int x=4; x<=8; x++){
if(board[by][x+1] || board[by+1][x+1]){
board[by][x] = 1;
board[by+1][x] = 1;
break;
}
//by 열이 비워져 있는 경우,
else if(x == 8){
board[by][9] = 1;
board[by+1][9] = 1;
}
}
//put block on green board
for(int y=4; y<=8; y++){
if(board[y+1][bx]){
board[y][bx] = 1;
board[y-1][bx] = 1;
break;
}
//bx 행이 비워져 있는 경우,
else if(y == 8){
board[8][bx] = 1;
board[9][bx] = 1;
}
}
}
(4) check_blue_board()
void check_blue_board(){
int x = 9;
bool check = true;
//9번 열부터, 6번 열까지 탐색
while(x >= 6){
//check = true -> x열에 블록이 꽉 찬 경우, check = false -> x열에 블록이 꽉 차있지 않은 경우,
check = true;
for(int y=0; y<4; y++){
//블록이 없는 칸이 있다면, false로 바꾼다
if(!board[y][x]) check = false;
}
//x열에 블록이 꽉 차 있지 않은 경우,
if(!check){
//이전 열을 탐색한다
x--;
continue;
}
//x열에 블록이 꽉 차 있는 경우, 점수가 1 증가한다
score++;
//4번째 열부터 8번째 열의 블록들을 오른쪽으로 한 열 땡긴다
for(int xx=x; xx>=5; xx--){
for(int y=0; y<4; y++){
board[y][xx] = board[y][xx-1];
}
}
//4번째 열의 블록을 비워준다
for(int y=0; y<4; y++){
board[y][4] = 0;
}
}
}
(5) check_green_board()
void check_green_board(){
int y = 9;
bool check = true;
//9번 행부터 6번 행까지 탐색
while(y >= 6){
//check = true -> y행에 블록이 꽉 찬 경우, check = false -> y행에 블록이 꽉 차있지 않은 경우,
check = true;
for(int x=0; x<4; x++){
//y행에 블록이 없는 칸이 있는 경우,
if(!board[y][x]) check = false;
}
//y행에 블록이 꽉 차있지 않은 경우,
if(!check){
//이전 행을 탐색한다
y--;
continue;
}
//y행에 블록이 꽉 찬 경우, 점수가 1 증가한다
score++;
//4번 행부터 8번 행의 블록을 아래로 한 행 땡긴다
for(int yy=y; yy>=5; yy--){
for(int x=0; x<4; x++){
board[yy][x] = board[yy-1][x];
}
}
//4번 행의 블록을 모두 비워준다
for(int x=0; x<4; x++){
board[4][x] = 0;
}
}
}
(6) check_sky_blue_board()
void check_sky_blue_board(){
int check = 0;
//연한 파란색 보드에 블록이 있는 행의 개수를 체크한다
for(int x=5; x>=4; x--){
for(int y=0; y<4; y++){
if(board[y][x]){
check++;
break;
}
}
}
switch(check){
//4, 5번 행 모두 블록이 없는 경우
case 0:
break;
//5번 행에 블록이 있는 경우
case 1:
//5번 행부터 8번 행의 블록을 아래로 한 행 땡긴다
for(int x=9; x>=6; x--){
for(int y=0; y<4; y++){
board[y][x] = board[y][x-1];
}
}
//5번 행의 블록을 모두 비운다
for(int y=0; y<4; y++){
board[y][5] = 0;
}
break;
//4, 5번 행 모두에 블록이 있는 경우
case 2:
//4번 행부터 7번 행의 블록을 아래로 두 행 땡긴다
for(int x=9; x>=5; x--){
for(int y=0; y<4; y++){
board[y][x] = board[y][x-2];
}
}
//4번, 5번 행의 블록을 모두 비운다
for(int x=4; x<=5; x++){
for(int y=0; y<4; y++){
board[y][x] = 0;
}
}
break;
}
}
(7) check_light_green_board()
void check_light_green_board(){
int check = 0;
//연한 초록색 보드에 블록이 있는 열의 개수를 체크한다
for(int y=5; y>=4; y--){
for(int x=0; x<4; x++){
if(board[y][x]){
check++;
break;
}
}
}
switch(check){
//연한 초록색 보드에 블록이 없는 경우
case 0:
break;
//5번 열에 블록이 있는 경우
case 1:
//5번 열부터 8번 열의 블록을 모두 오른쪽으로 한 열 땡긴다
for(int y=9; y>=6; y--){
for(int x=0; x<4; x++){
board[y][x] = board[y-1][x];
}
}
//5번 열의 블록을 모두 비운다
for(int x=0; x<4; x++){
board[5][x] = 0;
}
break;
//4, 5번 열에 모두 블록이 있는 경우
case 2:
//4번 열부터 7번 열의 블록을 모두 오른쪽으로 두 열 땡긴다
for(int y=9; y>=5; y--){
for(int x=0; x<4; x++){
board[y][x] = board[y-2][x];
}
}
//4, 5번 열의 블록을 모두 비운다
for(int y=4; y<=5; y++){
for(int x=0; x<4; x++){
board[y][x] = 0;
}
}
break;
}
}#include <iostream>
#include <vector>
using namespace std;
int N;
/*
red board -> 0<=x<=3, 0<=y<=3
blue board -> 6<=x<=9, 0<=y<=3
sky blue board -> 4<=x<=5, 0<=y<=3
green board -> 0<=x<=3, 6<=y<=9
light green board -> 0<=x<=3, 4<=y<=5
*/
int board[10][10] = {0, };
struct Block{
int t;
int x;
int y;
};
Block b;
vector<Block> blocks;
int score = 0;
int blue_blocks = 0;
int green_blocks = 0;
void put_block1(int bx, int by){
//put block on blue board
for(int x=4; x<=8; x++){
if(board[by][x+1]){
board[by][x] = 1;
break;
}
else if(x == 8){
board[by][9] = 1;
}
}
//put block on green board
for(int y=4; y<=8; y++){
if(board[y+1][bx]){
board[y][bx] = 1;
break;
}
else if(y == 8){
board[9][bx] = 1;
}
}
}
void put_block2(int bx, int by){
//put block on blue board
for(int x=4; x<=8; x++){
if(board[by][x+1]){
board[by][x] = 1;
board[by][x-1] = 1;
break;
}
else if(x == 8){
board[by][9] = 1;
board[by][8] = 1;
}
}
//put block on green board
for(int y=4; y<=8; y++){
if(board[y+1][bx] || board[y+1][bx+1]){
board[y][bx] = 1;
board[y][bx+1] = 1;
break;
}
else if(y == 8){
board[9][bx] = 1;
board[9][bx+1] = 1;
}
}
}
void put_block3(int bx, int by){
//put block on blue board
for(int x=4; x<=8; x++){
if(board[by][x+1] || board[by+1][x+1]){
board[by][x] = 1;
board[by+1][x] = 1;
break;
}
else if(x == 8){
board[by][9] = 1;
board[by+1][9] = 1;
}
}
//put block on green board
for(int y=4; y<=8; y++){
if(board[y+1][bx]){
board[y][bx] = 1;
board[y-1][bx] = 1;
break;
}
else if(y == 8){
board[8][bx] = 1;
board[9][bx] = 1;
}
}
}
void check_blue_board(){
int x = 9;
bool check = true;
while(x >= 6){
check = true;
for(int y=0; y<4; y++){
if(!board[y][x]) check = false;
}
if(!check){
x--;
continue;
}
score++;
for(int xx=x; xx>=5; xx--){
for(int y=0; y<4; y++){
board[y][xx] = board[y][xx-1];
}
}
for(int y=0; y<4; y++){
board[y][4] = 0;
}
}
}
void check_green_board(){
int y = 9;
bool check = true;
while(y >= 6){
check = true;
for(int x=0; x<4; x++){
if(!board[y][x]) check = false;
}
if(!check){
y--;
continue;
}
score++;
for(int yy=y; yy>=5; yy--){
for(int x=0; x<4; x++){
board[yy][x] = board[yy-1][x];
}
}
for(int x=0; x<4; x++){
board[4][x] = 0;
}
}
}
void check_sky_blue_board(){
int check = 0;
for(int x=5; x>=4; x--){
for(int y=0; y<4; y++){
if(board[y][x]){
check++;
break;
}
}
}
switch(check){
case 0:
break;
case 1:
for(int x=9; x>=6; x--){
for(int y=0; y<4; y++){
board[y][x] = board[y][x-1];
}
}
for(int y=0; y<4; y++){
board[y][5] = 0;
}
break;
case 2:
for(int x=9; x>=5; x--){
for(int y=0; y<4; y++){
board[y][x] = board[y][x-2];
}
}
for(int x=4; x<=5; x++){
for(int y=0; y<4; y++){
board[y][x] = 0;
}
}
break;
}
}
void check_light_green_board(){
int check = 0;
for(int y=5; y>=4; y--){
for(int x=0; x<4; x++){
if(board[y][x]){
check++;
break;
}
}
}
switch(check){
case 0:
break;
case 1:
for(int y=9; y>=6; y--){
for(int x=0; x<4; x++){
board[y][x] = board[y-1][x];
}
}
for(int x=0; x<4; x++){
board[5][x] = 0;
}
break;
case 2:
for(int y=9; y>=5; y--){
for(int x=0; x<4; x++){
board[y][x] = board[y-2][x];
}
}
for(int y=4; y<=5; y++){
for(int x=0; x<4; x++){
board[y][x] = 0;
}
}
break;
}
}
void monominodomino(){
for(int i=0; i<blocks.size(); i++){
b = blocks[i];
//put block
switch(b.t){
case 1:
put_block1(b.x, b.y);
break;
case 2:
put_block2(b.x, b.y);
break;
case 3:
put_block3(b.x, b.y);
break;
}
//check board
check_blue_board();
check_green_board();
check_sky_blue_board();
check_light_green_board();
}
}
int get_blocks(){
//get blocks on blue block
for(int y=0; y<4; y++){
for(int x=6; x<=9; x++){
blue_blocks += board[y][x];
}
}
//get blocks on green block
for(int y=6; y<=9; y++){
for(int x=0; x<4; x++){
green_blocks += board[y][x];
}
}
return blue_blocks+green_blocks;
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int i=0; i<N; i++){
cin >> b.t >> b.y >> b.x;
blocks.push_back(b);
}
monominodomino();
cout << score << endl;
cout << get_blocks() << endl;
return 0;
}
//시간복잡도 = O(N), 공간복잡도 = O(N)
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 20056 마법사 상어와 파이어볼 C++ (0) | 2021.10.14 |
|---|---|
| 백준 21609 상어 중학교 C++ (0) | 2021.10.14 |
| 백준 12015 가장 긴 증가하는 부분 수열 2 Python 3 (0) | 2021.10.08 |
| 백준 14002 가장 긴 증가하는 부분 수열 4 Python 3 (0) | 2021.10.06 |
| 백준 17825 주사위 윷놀이 C++ (0) | 2021.10.06 |