문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
- 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
- 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
- 격자에 중력이 작용한다.
- 격자가 90도 반시계 방향으로 회전한다.
- 다시 격자에 중력이 작용한다.
격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.
다음은 N = 5, M = 3인 경우의 예시이다.
| 2 | 2 | -1 | 3 | 1 |
| 3 | 3 | 2 | 0 | -1 |
| 0 | 0 | 0 | 1 | 2 |
| -1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 2 | 2 | 1 |
여기서 찾을 수 있는 크기가 가장 큰 블록 그룹을 다음과 같이 빨간색으로 표시했다.
| 2 | 2 | -1 | 3 | 1 |
| 3 | 3 | 2 | 0 | -1 |
| 0 | 0 | 0 | 1 | 2 |
| -1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 2 | 2 | 1 |
블록 그룹이 제거되면 다음과 같이 변하고, 점수 82점을 획득한다.
| 2 | 2 | -1 | 3 | 1 |
| 2 | 0 | -1 | ||
| 1 | 2 | |||
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 1 |
중력이 작용하면 다음과 같이 변한다.
| -1 | 3 | 1 | ||
| 0 | -1 | |||
| 2 | 2 | 1 | 2 | |
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 2 | 1 |
90도 반시계방향으로 회전한 결과는 다음과 같다.
| 1 | -1 | 2 | 2 | 1 |
| 3 | 0 | 1 | 3 | 2 |
| -1 | 2 | 1 | 2 | |
| 2 | ||||
| 2 | -1 |
다시 여기서 중력이 작용하면 다음과 같이 변한다.
| 1 | -1 | |||
| 3 | 2 | 2 | 1 | |
| -1 | 1 | 3 | 2 | |
| 2 | 1 | 2 | ||
| 0 | 2 | -1 | 2 |
오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.
입력
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다.
제한
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 5
package Samsung;
import java.util.*;
import java.io.*;
public class 상어중학교 {
static int n,m;
static int[][]arr;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int answer=0;
static class Pair{
int x,y;
Pair(int x, int y){
this.x =x;
this.y =y;
}
}
public static void print() {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
public static boolean cango(int x, int y) {
return x>=0 && x<n && y>=0 && y<n;
}
static ArrayList<Pair>blist; //선택된 블록집합의 좌표 리스트
public static void findBlock() {
int mx =0;
int my=0;
int mrainbow =0;
int msz =0;
boolean [][]check= new boolean[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(arr[i][j]>0 && !check[i][j]) { //일반 블록을 찾게되면 주변 블록 탐색 시작
Queue<Pair>q = new LinkedList<>();
ArrayList<Pair>list = new ArrayList<>(); //블록들의 좌표 리스트를 구한다.
Pair p = new Pair(i,j);
q.add(p);
list.add(p);
check[i][j]=true;
int col = arr[i][j];
int sz =1;
int rainbow =0;
ArrayList<Pair>rainbowlist = new ArrayList<>(); //무지개의 좌표들을 저장한다.
while(!q.isEmpty()){
Pair e = q.poll();
int x = e.x;
int y = e.y;
for(int t=0; t<4; t++){
int nx = x+dx[t];
int ny = y+dy[t];
if(cango(nx,ny)&&(arr[nx][ny]==col||arr[nx][ny]==0)&&!check[nx][ny]) { //일반블록 색이 같고 무지개 블록일때
if(arr[nx][ny]==0) { rainbowlist.add(new Pair(nx,ny)); rainbow++;}
Pair np = new Pair(nx,ny);
q.add(np);
list.add(np);
check[nx][ny]=true;
sz++;
}
}
}
for(Pair pt : rainbowlist) {
check[pt.x][pt.y]=false; //무지개 블록은 저장을 해두었다가 bfs 탐색이 끝나면 check배열을 false로 만들어줘야한다! -> 이부분은 직접 테케를 생각해서 코드를 짜야하는 부분이다.
}
if(sz<2) {continue;}
if(sz>msz) { //최대 크기보다 더 블록집합의 크기가 클 경우
msz=sz;
mx=i;
my=j;
mrainbow = rainbow;
blist = list;
}
else if(sz==msz) {
if(mrainbow<rainbow) {//크기가 같으면 무지개색 블록의 개수가 큰것을 선택
mx=i;
my=j;
mrainbow = rainbow;
blist = list;
}
else if(mrainbow==rainbow) { //무지개 블록의 개수가 같을때
if(mx<i) { //행좌표가 큰걸 선택
mx=i;
my=j;
blist = list;
}
else if(mx==i) {
if(my<j) {
mx =i;
my=j;
blist = list;
}
}
}
}
}
}
}
}
public static void simulate() {
int sz = blist.size();
answer += (sz*sz);
for(int i=0; i<blist.size(); i++) {
int x = blist.get(i).x;
int y = blist.get(i).y;
arr[x][y]=-2;
}
/*어려웠던점: 블록내려가는 코드 짜기*/ //2048 다시 풀어보기
for(int j=0; j<n; j++) {
int l =n-2;
while(l>=0) {
if(arr[l][j]>=0) {
int t = l;
t++;
while(cango(t,j)) {
if(arr[t][j]!=-2)break;
t++;
}
t--;
arr[t][j]=arr[l][j];
if(t!=l)arr[l][j]=-2; //주의! 아래의 블록에 다른 것이 있거나 바닥이어서 더이상 못내려 갈때는 그대로 두고 내려갔을때는 비어있는 칸으로 둔다.
}
l--;
}
}
/*어려웠던점: 회전하는 코드를 짤때는 새로운 2차원배열에 행을 열로 바꾸는 식으로 구현을 한다.*/
int[][]tmp = new int[n][n];
for(int i=n-1; i>=0; i--) {
int[] l = arr[i];
for(int j=n-1; j>=0; j--) {
tmp[j][i]=l[n-1-j];
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
arr[i][j]=tmp[i][j];
}
}
for(int j=0; j<n; j++) {
int l =n-2;
while(l>=0) {
if(arr[l][j]>=0) {
int t = l;
t++;
while(cango(t,j)) {
if(arr[t][j]!=-2)break;
t++;
}
t--;
arr[t][j]=arr[l][j];
if(t!=l)arr[l][j]=-2;
}
l--;
}
}
//System.out.println("==========중력후===========");
//print();
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][n];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
arr[i][j]=Integer.parseInt(st.nextToken());
}
}
while(true) {
blist = new ArrayList<>();
findBlock();
if(blist.size()==0)break;
simulate();
}
System.out.println(answer);
}
}1. 어려웠던점1: 블록내려가는 코드 짜기 -> 2048 다시 풀어보기
-> 주의! 아래의 블록에 다른 것이 있거나 바닥이어서 더이상 못내려 갈때는 그대로 두고 내려갔을때는 비어있는 칸으로 둔다.
2. 어려웠던점2: 회전하는 코드를 짤때는 새로운 2차원배열에 행을 열로 바꾸는 식으로 구현을 한다.
3. 어려웠던점3: 무지개 블록은 저장을 해두었다가 bfs 탐색이 끝나면 check배열을 false로 만들어줘야한다! -> 이부분은 직접 테케를 생각해서 코드를 짜야하는 부분이다.
'백준 > 삼성기출' 카테고리의 다른 글
| 미세먼지안녕-17144번(JAVA) (0) | 2021.09.25 |
|---|---|
| 상어초등학교 - 21608번 (JAVA) (0) | 2021.09.25 |
| 마법사상어와파이어스톰 - 20058번(Java) (0) | 2021.09.23 |
| 마법사상어와토네이도-20057번(Java) (0) | 2021.09.22 |
| 스타트택시 - 1923번(Java) (0) | 2021.09.18 |
