백준 20061 모노미노도미노 2 - 삼성 SW 역량 테스트 기출

백준 20061 모노미노도미노 2 - 삼성 SW 역량 테스트 기출

1. 문제 링크

https://www.acmicpc.net/problem/20061

20061번: 모노미노도미노 2

 

2. 문제 해결에 대한 아이디어

1. 이 문제를 시험장에서 만났다면, 다른 문제를 풀었을 것이다.

2. 블록은 1 x 1 / 1 x 2 / 2 x 1 의 총 3개로 주어진다.

3. 빨간 보드에 위치한 블록은 초록, 파랑 보드로 각각 이동한다.(그래서 각각 구현했다.)

4. 각 보드에서 블록의 움직임은 아래와 같다. (파란색 기준)

   . 경계를 만나거나 다른 블록을 만나기전까지 이동

      . 이 때, 블록은 조각 나서 움직일 수 없다. 한꺼번에 이동해야한다.

      . ex) 2 x 1(세로로 두 칸) 블록이 파랑 보드로 이동할 때, 각각 1 x 1로 조각나서 움직일 수 없다. (테트리스와 동일)

      . 따라서 파랑일 때는 3번, 초록일 때는 2번 블록의 움직임에 따로 고려했다.

         . 코드 내 finalX, finalY 참고

   . 꽉 찬 열을 지우고 지워진 열 기준으로 앞에 있는 것들을 이동시킨다. (delAndMoveBlue())

   . 연한 색(special)의 열 중 빈칸이 아닌 열의 갯수만큼 땡긴다. (specialBlue())

5. 처음 빨강에서 파랑 혹은 초록으로 블록이 이동할 때에 대해서 생각해봤다.

   . 행 혹은 열이 사라져서 이동하는 것처럼 구현할 수 있을까 생각해봤는데 아닌 것 같다.

   . 블록을 조각내서 움직이되, 최종적으로는 블록 전체가 움직인 상태로 처리하는게 나을 것 같다.

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	static class Block {
		int no, y, x;

		public Block(int no, int y, int x) {
			super();
			this.no = no;
			this.y = y;
			this.x = x;
		}

		public Block(Block b) {
			super();
			this.no = b.no;
			this.y = b.y;
			this.x = b.x;
		}

	}

	static int[][] red, blue, green;
	static int N;
	static ArrayList<Block> blockList = new ArrayList<>();
	static int score = 0;
	static int blockCount = 0;
	static int count = 1;

	public static void main(String[] args) throws Exception {
		BufferedReader br;
//		br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\모노미노도미노2_20061\\input.txt"));
		br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().split(" ")[0]);
		for (int i = 0; i < N; i++) {
			String[] txy = br.readLine().split(" ");
			int t = Integer.parseInt(txy[0]);
			int y = Integer.parseInt(txy[1]);
			int x = Integer.parseInt(txy[2]);
			blockList.add(new Block(t, y, x));
		}

		blue = new int[4][6];
		green = new int[6][4];

		for (int i = 0; i < blockList.size(); i++) {
			Block b = blockList.get(i);
			ArrayList<Block> temp = new ArrayList<>();
			if (b.no == 1) {
				temp.add(new Block(b.no, b.y, b.x));
			} else if (b.no == 2) {
				temp.add(new Block(b.no, b.y, b.x + 1));
				temp.add(new Block(b.no, b.y, b.x));

			} else if (b.no == 3) {
				temp.add(new Block(b.no, b.y + 1, b.x));
				temp.add(new Block(b.no, b.y, b.x));
			}

			blue(temp);
			green(temp);

			count++;
		}
		blockCount();

		System.out.println(score);
		System.out.println(blockCount);
	}

	static void green(ArrayList<Block> temp) {
		toGreen(temp);
		delAndMoveGreen();
		specialGreen();
	}

	static void toGreen(ArrayList<Block> temp) {
		// 아래로 이동할꺼니까 y 에 1을 계속 더해줌
		int finalY = 6; // 2번 블록 (가로 2칸)이 동시에 움직이게 하기위함
		int blockNo = 0;

		for (int i = 0; i < temp.size(); i++) {
			Block b = temp.get(i);
			int y = 0;
			int x = b.x;
			blockNo = b.no;
			++y;

			while (y != 6 && green[y][x] == 0) {
				++y;
			}
			--y;

			if (blockNo != 2) {
				green[y][x] = b.no;
			} else {
				if (finalY > y) {
					finalY = y;
				}
			}

		}

		if (blockNo == 2) {
			for (int i = 0; i < temp.size(); i++) {
				Block b = temp.get(i);
				int x = b.x;
				green[finalY][x] = b.no;
			}
		}
	}

	static void delAndMoveGreen() {
		for (int i = 5; i >= 2; i--) {
			boolean del = true;
			for (int j = 0; j < 4; j++) {
				if (green[i][j] == 0) {
					del = false;
					break;
				}
			}
			if (del) {
				for (int j = 0; j < 4; j++) {
					for (int k = i - 1; k >= 0; k--) {
						green[k + 1][j] = green[k][j];
						if (k == 0)
							green[k][j] = 0;
					}
				}
				++i;
				++score;
			}
		}
	}

	static void specialGreen() {

		int specialCnt = 0;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 4; j++) {
				if (green[i][j] != 0) {
					++specialCnt;
					break;
				}
			}
		}
		if (specialCnt == 0)
			return;

		for (int i = 5 - specialCnt; i >= 0; i--) {
			for (int j = 0; j < 4; j++) {
				green[i + specialCnt][j] = green[i][j];
			}
		}

		for (int i = 0; i < specialCnt; i++) {
			for (int j = 0; j < 4; j++) {
				green[i][j] = 0;
			}
		}
	}

	static void blue(ArrayList<Block> temp) {
		toBlue(temp);
		delAndMoveBlue();
		specialBlue();
	}

	static void toBlue(ArrayList<Block> temp) {
		// 오른쪽으로 이동할꺼니까 x 에 1을 계속 더해줌
		int finalX = 6;
		int blockNo = 0;
		for (int i = 0; i < temp.size(); i++) {
			Block b = temp.get(i);
			blockNo = b.no;
			int y = b.y;
			int x = 0;
			++x;
			while (x != 6 && blue[y][x] == 0) {
				++x;
			}
			--x;

			if (blockNo != 3) {
				blue[y][x] = b.no;
			} else {
				// 2 * 1 블록을 통째로 옮기기 위함
				if (finalX > x) {
					finalX = x;
				}
			}
		}
		// 2 * 1 블록
		if (blockNo == 3) {
			for (int i = 0; i < temp.size(); i++) {
				Block b = temp.get(i);
				int y = b.y;

				blue[y][finalX] = b.no;
			}
		}

	}

	static void delAndMoveBlue() {
		for (int j = 5; j >= 2; j--) {
			boolean del = true;
			for (int i = 0; i < 4; i++) {
				if (blue[i][j] == 0) {
					del = false;
					break;
				}
			}
			if (del) {
				for (int i = 0; i < 4; i++) {
					for (int k = j - 1; k >= 0; k--) {
						blue[i][k + 1] = blue[i][k];
						if (k == 0)
							blue[i][k] = 0;
					}
				}
				++j;
				++score;

			}
		}

	}

	static void specialBlue() {
		int specialCnt = 0;
		for (int j = 0; j < 2; j++) {
			for (int i = 0; i < 4; i++) {
				if (blue[i][j] != 0) {
					++specialCnt;
					break;
				}
			}
		}
		if (specialCnt == 0)
			return;

		for (int i = 0; i < 4; i++) {
			for (int j = 5 - specialCnt; j >= 0; j--) {
				blue[i][j + specialCnt] = blue[i][j];
			}
		}

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < specialCnt; j++) {
				blue[i][j] = 0;
			}
		}
	}

	static void blockCount() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 6; j++) {
				if (blue[i][j] != 0)
					++blockCount;
			}
		}

		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 4; j++) {
				if (green[i][j] != 0)
					++blockCount;
			}
		}
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 이 문제는 파랑, 초록에 대한 각각의 구현이 필요했다.

2. 처음 파랑 초록으로 이동하는 블록을 한꺼번에 움직이는게 관건이었다. (시간 많이 뺏김)

3. 행 혹은 열을 움직일 때 기존 보드에서만 하는 방법과 복사 보드에다가 기록 후, 원래 보드에 하는 방법을 사용했다.

   . 수행시간이나 메모리 측면에서 크게 차이가 나지 않았다.

   . 풀다가 둘 중 하나에서 막히면 다른 방법을 사용하는 것을 고려해봐야겠다.

   . 이 문제는 복사 보드를 사용할 필요는 없었다.