상어중학교

개괄적인 로직은 어느 정도 생각했다. 세부적인 조건이나 구현을 제대로 하지 못했다.

전체적인 구조 : 메인이 되는 solve 함수를 구현하고, 무한루프로 아래 연산을 반복한다. 1. findremoveBlock() : 블록 그룹을 찾아서 블록을 제거, 점수 합산. => 연산을 반복하는 조건이 되기 때문에, 블록 그룹을 탐색&제거 하면 true를 리턴하고, 그렇지 못하면 false를 리턴해서 전체 연산 반복을 종료한다! 2. gravity() : 좌표값들을 아래 방향으로 이동시킨다. => 범위초과 체크, 블록이 없는 칸이면 1칸씩 이동을 반복 : 2차원 배열 순회하면서 2중 for문 안에 while문을 만들어 아래로 계속 이동하는 반복문을 구성했다. => 블록 삭제해서 없는 칸을 100이라고 한다면, M이하의 모든 칸들은 블록이 있는 칸들이기 때문에, 다음 칸의 배열 값이 M이하일 때만 아래로 이동시킨다. ✅이동시킬 때 주의점! 배열 값 몇번 회전/이동시켜보니, 제일 마지막으로 변하는 값을 가장 먼저 처리해줘야한다! 따라서, 가장 마지막 행에 있는 값이 마지막에 변화하기 때문에 감소 반복문으로 구현해야한다고 생각했다. 3. rotate() : 2차원 배열 반시계 방향 회전. 로직 이해✅(아주 쉽고 간단했음)

void solve()  {
    while(true) {
        if(findremoveBlock() == false) break;
        gravity();
        rotate();
        gravity();
    }
}

rotate() :

private static void leftRotate() {
        int[][] mapClone = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                mapClone[i][j] = map[j][N-1-i];
            }
        }
        for (int i = 0; i < N; i++) {
            System.arraycopy(mapClone[i], 0, map[i], 0, N);
        }
    }

생각하지 못한 부분

크기가 가장 큰 블록 그룹을 찾아서 갯수를 세야하기 때문에 BFS를 해야겠다는 생각은 했지만, 어떻게 구현해야할지 감을 못 잡았었다. => 문제에서 정의하는 블록 그룹의 "기준 블록" : 블록그룹에서 무지개 블록이 아닌 블록 중, 행번호가 가장 작은 블록, 여러개면 열번호 가장 작은 블록이다. 따라서, 행과 열번호가 가장 작은 블록이기 때문에, 블록 그룹을 탐색하는 시작점을 의미한다!⭐️ 그리고, BFS를 계속해서 반복하는데, 이 때 블록 그룹 기준 블록이 BFS 시작점이 된다!

2차원 배열 회전 마스터

  1. 정사각형 배열 NxN 회전 ① 90° 반시계 회전 : newMap[i][j] = map[j][N-1-i]

    private static void leftRotate() {
        int[][] mapClone = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                mapClone[i][j] = map[j][N-1-i];
            }
        }
        for (int i = 0; i < N; i++) {
            System.arraycopy(mapClone[i], 0, map[i], 0, N);
        }
    }

    ② 90° 시계 회전 : newMap[i][j] = map[N-1-j][i]

    private static void rightRotate() {
        int[][] mapClone = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                mapClone[i][j] = map[N-1-j][i];
            }
        }
        for (int i = 0; i < N; i++) {
            System.arraycopy(mapClone[i], 0, map[i], 0, N);
        }
    }

  2. 직사각형 배열 NxM 회전(4x5 배열 회전 => 5x4배열) 핵심은 RxC => CxR이 되고, 반복문 구성 또한 변수 바뀐다는 것!

    ① 90° 반시계 회전 : newRect[i][j] = reect[j][C-1-i] 반복문 구성은 기존 정사각형 회전과 동일하게 새로운 배열 기준으로 행부터 차례대로 채워지고,

    기존 정사각형 배열과 달라진 점이라면, 기존 배열에서 열 위치가 N-1-i에서 C-1-i로 바뀌었다. 기존 배열의 열 좌표를 기준으로, 제일 끝 열(C-1)부터 시작해서 새로운 배열 첫번째(0번째) 행부터 채우지기 시작하기 때문이다!

    1. private static void leftRotate() {
    int[][] newRect = new int[rectC][rectR];//4*5 => 5*4
		for(int i=0;i<rectC;i++) {//squareR = squareC 이므로 동일한 변수로 2중 반복문 구성.
			for(int j=0;j<rectR;j++) {
				newRect[i][j] = rect[j][rectC-1-i];//기존 : N-1-i에서 N이 기존 배열의 열(rectC)로 바뀌었다!
			}
		}
}

    ② 90° 시계 회전

    1. private static void rightRotate() {
    int[][] rightRect = new int[rectC][rectR];//4*5 => 5*4 
		for(int i=0;i<rectC;i++) {//squareR = squareC 이므로 동일한 변수로 2중 반복문 구성.
			for(int j=0;j<rectR;j++) {
				rightRect[i][j] = rect[rectR-1-j][i];
			}
		}
}

2차원 배열 회전 로직 한줄 정리 NxN 배열 회전하는 것을 기준으로 생각하면 생각을 확장하기 쉽다. 새로운 배열의 첫번째행부터 시작해서 채우는 인덱스로 반복문을 구성한다.(위의 그림 참고) 반복변수 i,j 에 따라서 기존 배열에서 복사하는 행 또는 열 값이 고정되는 값이 존재하고, 변수에 따라서 기존 배열에서 변하는 인덱스값이 존재한다. =>시뮬레이션 조금만 해보면 고정되는 인덱스, i,j에 따라 변하는 인덱스 알 수 있다!

솔루션 문제에서 나온 오토플레이 동작 설명 그대로 구현대로 하면 된다. 크기가 가장 큰 블록 그룹을 찾을 때, 크기가 동일하다면 포함된 무지개 칸 갯수가 가장 많은 것, 여러개면 행이 가장 큰 것, 그것도 여러개면 열이 가장 큰 것을 찾는다!

문제 재정의, 추상화

  1. 2차원 배열 순회하면서 가장 큰 크기의 블록그룹 BFS 탐색! : 2중 for문, 큐 이용 문제 조건에 따라 검은색 블록(-1)은 포함하면 안 되고, 무지개 블록(0) 또는 일반 블록(M이하 자연수)만 해당된다. - 탐색 조건 시, 배열 값 체크 : 0보다 크고 M이하인지 확인한다! : 무지개인 칸은 왜 조건 체크안 해주지?🧐 => 일단 일반 블록을 대상으로 탐색을 시작하고, 인접노드 방문하려 큐에 삽입할 때, 이 때 무지개인 칸 조건 넣어서 탐색해주도록 한다! 기준 블록 : 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록! 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이기 때문에, 0이 아니고, 행과 열이 가장 작은 칸이다. =>2차원 배열 순회하는 2중 for문에서 처음으로 나오는 0, -1이 아닌 좌표에 대해 기준 블록으로 설정해준다! =>기준 블록은 블록 그룹을 찾기 위한 탐색 시작점이 된다! (큐에 제일 처음 들어가는 좌표)

  2. 최대 갯수 블록 그룹으로 갱신 : 블록 갯수, 무지개 블록 갯수, 기준 블록의 행값, 기준 블록의 열값 큰 것으로 갱신, 최대 갯수가 2개 이상인지 확인.

  3. 점수 합산

  4. 최종 갱신된 블록그룹에 속하는 블록들(좌표칸) 삭제 처리 : 6으로 마킹.

Previous어른 상어Next구슬 탈출2

Last updated