20061 모노미노도미노 2 : https://www.acmicpc.net/problem/20061
Problem
Solve
구현한 코드가 좀 길어서 다르게 구현하는 방법이있을까 하고 찾아봤지만 다른 분들도 그냥 구현하면 된다. 라고 했기 때문에 다른 분들이 나보다 최적화를 잘했구나 라고 생각했다.
모노미노도미노의 보드는 10*10 크기의 2차원 배열로 이루어져있고 (0,0)부터 (3,3)까지는 빨간 보드, (0,4)부터 (3,9)까지는 파란 보드, (4,0)부터 (9,3)까지는 초록 보드로 이루어져있다.
블럭은 t=1일때 11크기, t=2일때 12, t=3일때 2*1의 형태를 가지고 있다.
주어진 블럭을 움직일때 초록 보드와 파란 보드로 이동하는 함수(move), 초록 보드와 파란 보드에 각각 행과 열이 꽉차있는지 확인 후 삭제하여 score를 구하는 함수(scoreCount), 4행,5행의 연두색 부분과 4열, 5열의 하늘색 부분에 블럭이 있는지 확인하고 있다면 그만큼 블럭을 삭제하는 함수(speicalCount)를 반복하여 구현하였다.
- 이동 함수(move)
- t=1일때 1*1 블럭 이동(초록 보드, 파란 보드)
- 2차원 배열 범위를 벗어나지 않고 블럭을 이동하면서 다른 블럭을 만나기 전까지 이동
- t=2일때 1*2 블럭 이동(초록 보드, 파란 보드)
- 두개의 1*1 블럭이 이동할때 둘중 하나의 블럭이 다른 블럭을 만나기 전까지 이동
- t=3일대 2*1 블럭 이동(초록 보드, 파란 보드)
- 두개의 1*1 블럭이 이동할때 둘중 하나의 블럭이 다른 블럭을 만나기 전까지 이동
- t=1일때 1*1 블럭 이동(초록 보드, 파란 보드)
- 점수 함수(scoreCount)
- 초록보드는 하나의 행에 블럭이 모두 존재하면 score+1, 파란보드는 하나의 열에 블럭이 모두 존재하면 score+1
- 행과 열을 마지막 부터 돌면서 확인하면서 블럭이 한 줄씩 삭제가 되면 score+1과 그 위의 블럭을 한칸 이동시켜주며 반복한다.
이때 주의 해야할 점은 블럭을 한 줄 씩 삭제하여 블럭을 이동시켜주어도 블럭이 가득 찬 경우가 없을때 까지 점수를 획득하는 과정이 모두 진행되어야 한다.- 그렇기 때문에 while문을 통해 초록 보드와 파란 보드에 모든 범위에 블럭이 가득 찬 경우가 없을때까지 반복해줘야한다.(이 조건을 만족시키는 코드가 없어서 하루를 날렸다..)
- 특수 범위의 블럭 삭제 함수(specialCount)
- 초록 보드에서
4행과 5행에 블럭이 하나라도 있다면블럭이 존재하는각 행의 개수만큼 마지막 행을 지워서 블럭들을 아래쪽으로 이동시켜야한다. - 마찬가지로 파란 보드에서
4열과 5열에 블럭이 하나라도 있다면블럭이 존재하는각 행의 개수만큼 마지막 열을 지워 블럭들을 오른쪽으로 이동시켜야한다.
- 초록 보드에서
모든 과정을 거쳐 주어진 블럭을 이동시켰다면 현재 상태에서 초록 보드와 파란 보드에 있는 블럭의 개수를 구해 위의 과정에서 구한 score와 함께 반환해준다.
Code
public class 모노미노도미노2 {
static int N;
static int[][] board;
static int[][] blocks;
static int totalScore;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
//(0,0)부터 (3,3)은 빨간 보드
//(0,4)부터 (3,9)는 파란 보드
//(4,0)부터 (9,3)은 초록 보드
//(4,4)부터 (9,9)는 사용하지 않는 범위
board = new int[10][10];
blocks = new int[N][4];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int t = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
blocks[i][0] = t;
blocks[i][1] = x;
blocks[i][2] = y;
}
totalScore = 0;
for (int t = 0; t < N; t++) {
//이동함수
move(t);
//점수 합산 함수
scoreCount();
//특수 범위 블럭 삭제 함수
specialCount();
}
//파란 보드와 초록 보드에 남아있는 블럭 개수 함수
int blockCount = blockCount();
StringBuilder sb = new StringBuilder();
sb.append(totalScore);
sb.append("\n");
sb.append(blockCount);
bw.write(sb.toString());
bw.flush();
bw.close();
}
//초록 보드, 파란 보드에 남아있는 블럭 개수 함수
static int blockCount() {
int count = 0;
for (int x = 6; x < 10; x++) {
for (int y = 0; y < 4; y++) {
if (board[x][y] != 0) {
count++;
}
}
}
for (int y = 6; y < 10; y++) {
for (int x = 0; x < 4; x++) {
if (board[x][y] != 0) {
count++;
}
}
}
return count;
}
static void specialBlueCount() {
//4열, 5열을 확인하여 블럭이 존재하는 열의 개수만큼 맨 아래 블럭부터 삭제하여 오른쪽으로 이동
int count = 0;
for (int y = 4; y <= 5; y++) {
for (int x = 0; x < 4; x++) {
if (board[x][y] != 0) {
count++;
break;
}
}
}
if (count == 0)
return;
for (int y = 9 - count; y >= 4; y--) {
for (int x = 0; x < 4; x++) {
board[x][y + count] = board[x][y];
board[x][y] = 0;
}
}
}
static void specialGreenCount() {
//4행, 5행을 확인하여 블럭이 존재하는 행의 개수만큼 맨 아래 블럭부터 삭제하여 아래로 이동
int count = 0;
for (int x = 4; x <= 5; x++) {
for (int y = 0; y < 4; y++) {
if (board[x][y] != 0) {
count++;
break;
}
}
}
if (count == 0)
return;
for (int x = 9 - count; x >= 4; x--) {
for (int y = 0; y < 4; y++) {
board[x + count][y] = board[x][y];
board[x][y] = 0;
}
}
}
//특수 범위의 블럭 삭제 함수
static void specialCount() {
//하늘색 보드
specialBlueCount();
//연두색 보드
specialGreenCount();
}
//파란 보드의 행이 블럭으로 가득찼는지 확인
static int deleteBlueCheck() {
int score = 0;
while (true) {
boolean isAnyDelete = false;
for (int y = 9; y >= 6; y--) {
boolean isFull = true;
for (int x = 0; x < 4; x++) {
if (board[x][y] == 0) {
isFull = false;
break;
}
}
//해당 열에서 블럭으로 가득차있다면
if (isFull) {
isAnyDelete = true;
score++;
for (int i = y - 1; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
//블럭 이동
board[j][i + 1] = board[j][i];
board[j][i] = 0;
}
}
}
}
//파란 블럭의 모든 열에 블럭으로 가득차있는 열이 하나라도 없다면 반복문 종료
if(!isAnyDelete) break;
}
return score;
}
//초록 보드의 행이 블럭으로 가득찼는지 확인
static int deleteGreenCheck() {
int score = 0;
while (true) {
boolean isAnyDelete = false;
for (int x = 9; x >= 6; x--) {
boolean isFull = true;
for (int y = 0; y < 4; y++) {
if (board[x][y] == 0) {
isFull = false;
break;
}
}
//해당 행이 블럭으로 가득차있다면
if (isFull) {
isAnyDelete = true;
score++;
for (int i = x - 1; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
board[i + 1][j] = board[i][j];
board[i][j] = 0;
}
}
}
}
//초록 보드의 모든 행에 블럭으로 가득차있는 행이 하나라도 없다면 반복문 종료
if (!isAnyDelete)
break;
}
return score;
}
//점수 합산 함수
static void scoreCount() {
int score = 0;
//초록색 : 9행 부터 4행까지 확인하면서 해당 행이 꽉차있다면 행 지우고 score+1
score += deleteGreenCheck();
//파란색 : 9열부터 4열까지 확인하면서 해당 열이 꽉차있다면 열 지우고 score+1
score += deleteBlueCheck();
totalScore += score;
}
//이동 함수
static void move(int turn) {
int t = blocks[turn][0];
int x = blocks[turn][1];
int y = blocks[turn][2];
//1*1 블럭
if (t == 1) {
oneBlockGreenMove(x, y);
oneBlockBlueMove(x, y);
}
//1*2 블럭
else if (t == 2) {
widthBlueMove(x, y + 1);
widthGreenMove(x, y + 1);
}
//2*1 블럭
else {
lengthBlueMove(x + 1, y);
lengthGreenMove(x + 1, y);
}
}
//2*1블럭 오른쪽 이동
//매개변수로 받은 x,y는 2*1블럭에서 아래부분의 블럭 좌표
static void lengthBlueMove(int x, int y) {
while (y < 10 && (board[x - 1][y] == 0 && board[x][y] == 0)) {
y++;
}
y -= 1;
board[x - 1][y] = 1;
board[x][y] = 1;
}
//2*1블럭 아래 이동
//매개변수로 받은 x,y는 2*1블럭에서 아래부분의 블럭 좌표
static void lengthGreenMove(int x, int y) {
while (x < 10 && board[x][y] == 0) {
x++;
}
x -= 1;
board[x - 1][y] = 1;
board[x][y] = 1;
}
//1*2블럭 오른쪽 이동
//매개변수로 받은 x,y는 1*2블럭에서 오른쪽부분의 블럭 좌표
static void widthBlueMove(int x, int y) {
while (y < 10 && board[x][y] == 0) {
y++;
}
y -= 1;
board[x][y - 1] = 1;
board[x][y] = 1;
}
//1*2블럭 아래 이동
//매개변수로 받은 x,y는 1*2블럭에서 오른쪽부분의 블럭 좌표
static void widthGreenMove(int x, int y) {
while (x < 10 && (board[x][y - 1] == 0 && board[x][y] == 0)) {
x++;
}
x -= 1;
board[x][y - 1] = 1;
board[x][y] = 1;
}
//1*1블럭 오른쪽 이동
static void oneBlockBlueMove(int x, int y) {
while (y < 10 && board[x][y] == 0) {
y++;
}
y -= 1;
board[x][y] = 1;
}
//1*1블럭 아래 이동
static void oneBlockGreenMove(int x, int y) {
while (x < 10 && board[x][y] == 0) {
x++;
}
x -= 1;
board[x][y] = 1;
}
}
Result
역시 삼성기출문제집의 마지막에 다와갈수록 복잡하고 왜맞틀이 빈번하며 컴퓨터와 이야기하는 시간이 늘어가는걸 느끼고있다. 멘탈만 잡고 시간만 줄인다면 충분히 풀수있는 문제이다.
화이팅!
Reference
내 꿈은 좋은 개발자