[BOJ - JAVA] (삼성전자 기출) 21609 - 상어 중학교 (구현, 시뮬레이션, BFS)

# 주소

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

21609번: 상어 중학교

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Block{
    int x;
    int y;
    int sum;
    int rainbow;
    boolean[][] v;
    Block(int x, int y, int rainbow, int sum, boolean[][] v){
        this.x = x;
        this.y = y;
        this.rainbow = rainbow;
        this.sum = sum;
        this.v = v;
    }
}
public class 상어중학교 {
    static int n, m;
    static int[][] arr;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    static boolean[][] visit;
    static Queue<Block> queue;
    static int answer = 0;
    static List<Block> list; //영역을 list형태로 저장
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                arr[i][j] = scan.nextInt();
        //입력 끝
        while (true){
            list = new ArrayList<>();
            visit = new boolean[n][n];
            boolean[][] visit2;//찾아온 인근 블록이 조건에 맞으면 visit2에저장
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++) {
                    if (arr[i][j] > 0 && !visit[i][j]) {//이중for문을 돌며 bfs탐색
                        queue = new LinkedList<>();
                        visit[i][j] = true;
                        queue.offer(new Block(i, j, 0, 1, visit));
                        //visit도 파라미터에 넣은 이유는 list랑 같은 클래스를 공유하기 때문
                        bfs (i,j, arr[i][j]);//i행 j열에 arr[i][j]색넣고 bfs탐색 시작
                    }
                }
            //굳이 visit2를 쓰는 이유는, 무지개 블록은 중복해서 탐색할 수 있기 때문
            Collections.sort(list, new Comparator<Block>() {
                @Override
                public int compare(Block o1, Block o2) {
                    if(o1.sum == o2.sum){
                        if(o1.rainbow == o2.rainbow){
                            if(o1.x == o2.x){
                                return o2.y - o1.y;
                            }
                            return o2.x - o1.x;
                        }
                        return o2.rainbow - o1.rainbow;
                    }
                    return o2.sum - o1.sum;
                }
            });//list를 sum, rainbow, x, y에 맞게 내림차순 정렬
            if(list.size() == 0 || list.get(0).sum == list.get(0).rainbow || list.get(0).sum < 2)
                break;
            //가져온 구슬 영역 중 가장 조건에 부합한 것이 탐색 불가면 break
            visit2 = list.get(0).v.clone();
            answer += (int)Math.pow(list.get(0).sum, 2);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    if(visit2[i][j])
                        arr[i][j] = -2;
            //탐색 마친 visit2는 -2로 치환하고 answer에 값 더해줌
            gravity(); //중력 작용
            Queue<Integer> qq = new LinkedList<>();
            for(int i = n - 1; i >= 0; i--)
                for(int j = 0; j < n; j++)
                    qq.offer(arr[j][i]);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    arr[i][j] = qq.poll();
            //반시계방향으로 90도 회전
            gravity(); //중력 작용
        }
        System.out.println(answer);
    }
    static void bfs(int x, int y, int color){
        //무지개 블록과 일반 블록을 모두 탐색할 배열
        boolean[][] tempVisit = new boolean[n][n];
        int temp = 1; //전체 블록 개수
        int tempRainbow = 0;//무지개 블록 개수
        tempVisit[x][y] = true; //시작점 true로 바꾸기
        while (!queue.isEmpty()){
            Block now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if(tempVisit[nx][ny] || visit[nx][ny])
                    continue;
                if(arr[nx][ny] < 0)
                    continue;
                if(arr[nx][ny] == color) {
                    visit[nx][ny] = true;
                    tempVisit[nx][ny] = true;
                    queue.offer(new Block(nx, ny, now.rainbow, now.sum + 1, visit));
                    temp++;
                }//만약 color색과 같으면 visit, tempVisit모두 true
                else if(arr[nx][ny] == 0) {
                    tempVisit[nx][ny] = true;
                    queue.offer(new Block(nx, ny, now.rainbow + 1, now.sum + 1, visit));
                    temp++;
                    tempRainbow++;
                }//무지개 블록이면 tempVisit만 true, tempRainbow++
            }
        }
        list.add(new Block(x, y, tempRainbow, temp, tempVisit));
        /*
        x,y를 그대로 넣는 이유는 위에서 2중 for문을 통해, x,y가 작을수록
        기준 블록이 되기 때문에, 최초에 bfs탐색시작할 때 찾은 x,y가 그대로 기준블록이됨
        그러므로 한 번 bfs가 실행될때면 list에 한 번만 넣어주면 되고 그 때 무지개와 전체블록, 이 때의 visit배열을 넣음
         */
    }
    static void gravity(){
        //중력 적용은 밑에서 부터 탐색하여 위에서 내려올 것이 있으면 그대로 밑으로보냄
        for(int i = n - 1; i > 0; i--){
            for(int j = 0; j < n; j++){
                if(arr[i][j] == -2){
                    int nx = i;
                    Queue<Integer> temp = new LinkedList<>();
                    for(int t = i; t >= 0; t--){
                        if(arr[t][j] == -1)
                            break;
                        if(arr[t][j] >= 0) {
                            temp.add(arr[t][j]);
                            nx = t;
                            break;
                        }//내려올 블록을 찾았으면 temp에 일단 넣고 nx에 인덱스 저장
                    }
                    if(temp.size() > 0) {
                        arr[i][j] = temp.poll();
                        arr[nx][j] = -2;
                    }//내려올 블록이 있다면 기존 arr에 temp를 넣고 위의 인덱스는 -2넣음(temp안쓰고 변수에 담아서 저장해도됨)
                }
            }
        }
    }
}

주석 그대로 이해하셔도 난이도가 높지 않기 때문에 두셔도 되지만 확실히 구현문제는 상당히 신경써야할 부분이 많습니다.

삼성전자는 특히 고려해봄직하지 못한 반례 문제를 몇 개씩 테스트코드에 넣어서 그런지 예제는 다맞더라도 항상 90%나 50%에서 한 번씩 틀릴 때가 있어서 꼼꼼히 확인하는게 중요합니다 ㅠㅠ.

 

문제 요약을 하겠습니다.

# 문제 요약

1. Comparator를 이용한 인터페이스 정렬을 꼭 인지하셔야 쉽게 풀 수 있습니다.

2. bfs에서는 visit배열이 필수인데, 무지개 블록을 중복 visit처리하면 안되기 때문에 visit배열을 2개 쓰셔야 합니다.

3. bfs탐색시 탐색을 다 마치고 list에 저장

4. 반시계방향 회전시 실수 조심하기

5. 중력이 작용할 땐 밑에서부터 구현하기

 

이렇게 요약할 수 있겠습니다.

주석 처리된 부분이 이해 안가실 수 있어서 차근차근 서술하겠습니다.

class Block{
    int x;
    int y;
    int sum;
    int rainbow;
    boolean[][] v;
    Block(int x, int y, int rainbow, int sum, boolean[][] v){
        this.x = x;
        this.y = y;
        this.rainbow = rainbow;
        this.sum = sum;
        this.v = v;
    }
}

Block 클래스는 이렇게 구현했습니다.

v 배열은 나중에 탐색한 영역을 저장하기 위해 클래스에 같이 주입하였습니다.

다른 방식을 원하신다면 visit배열을 static하게 선언하셔서 탐색 후 블록 총 개수와 행, 열 ,무지개 블록 개수를 비교해가며 visit을 저장해도 됩니다. 저는 그냥 조금이라도 코드를 줄이고 싶어 이렇게 구현했습니다.

static int n, m;
static int[][] arr;
static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
static boolean[][] visit;
static Queue<Block> queue;
static int answer = 0;
static List<Block> list;

static으로는 다음과 같은 변수들을 사용하기 위해 선언하였습니다.

구현 문제에서 필수인 동서남북 방향 벡터(dir)는 이제는 안보고 치셔도 쓸 수 있을만큼 눈에 익으셔야합니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[n][n];
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        arr[i][j] = scan.nextInt();

입력으로는 n, m, arr를 입력받습니다.

 

list = new ArrayList<>();
visit = new boolean[n][n];
boolean[][] visit2;//찾아온 인근 블록이 조건에 맞으면 visit2에저장
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++) {
        if (arr[i][j] > 0 && !visit[i][j]) {//이중for문을 돌며 bfs탐색
            queue = new LinkedList<>();
            visit[i][j] = true;
            queue.offer(new Block(i, j, 0, 1, visit));
            //visit도 파라미터에 넣은 이유는 list랑 같은 클래스를 공유하기 때문
            bfs (i,j, arr[i][j]);//i행 j열에 arr[i][j]색넣고 bfs탐색 시작
        }
    }

이제 본격적으로 인근 영역을 찾아야 합니다.

따라서 루프가 돌 때마다 기준블록과 블록 개수, 무지개 블록 개수, 인근 영역 visit을 담을 list와 visit을 항상 새로 선언하셔야합니다.

visit2는 탐색을 마치고 행, 열, 블록 개수, 무지개 개수를 정렬한 영역을 담을 배열입니다.

2중 for문을 통해 탐색하여 일반 블록중(arr > 0) 방문하지 않은(!visit) 블록을 찾아, queue에 넣고 bfs문을 돌립니다.

 

 

static void bfs(int x, int y, int color){
    //무지개 블록과 일반 블록을 모두 탐색할 배열
    boolean[][] tempVisit = new boolean[n][n];
    int temp = 1; //전체 블록 개수
    int tempRainbow = 0;//무지개 블록 개수
    tempVisit[x][y] = true; //시작점 true로 바꾸기
    while (!queue.isEmpty()){
        Block now = queue.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                continue;
            if(tempVisit[nx][ny] || visit[nx][ny])
                continue;
            if(arr[nx][ny] < 0)
                continue;
            if(arr[nx][ny] == color) {
                visit[nx][ny] = true;
                tempVisit[nx][ny] = true;
                queue.offer(new Block(nx, ny, now.rainbow, now.sum + 1, visit));
                temp++;
            }//만약 color색과 같으면 visit, tempVisit모두 true
            else if(arr[nx][ny] == 0) {
                tempVisit[nx][ny] = true;
                queue.offer(new Block(nx, ny, now.rainbow + 1, now.sum + 1, visit));
                temp++;
                tempRainbow++;
            }//무지개 블록이면 tempVisit만 true, tempRainbow++
        }
    }
    list.add(new Block(x, y, tempRainbow, temp, tempVisit));
    /*
    x,y를 그대로 넣는 이유는 위에서 2중 for문을 통해, x,y가 작을수록
    기준 블록이 되기 때문에, 최초에 bfs탐색시작할 때 찾은 x,y가 그대로 기준블록이됨
    그러므로 한 번 bfs가 실행될때면 list에 한 번만 넣어주면 되고 그 때 무지개와 전체블록, 이 때의 visit배열을 넣음
     */

bfs문의 내부는 다음과 같습니다.

이 때 중요한 것이 tempVisit을 또 선언한 것을 확인할 수 있는데, 이것은 무지개 블록이 탐색되는 것이 다른 bfs때 겹치면 안되기 때문에 분리해주기 위해 따로 사용합니다.

temp는 1, tempRainbow는 0으로 시작하고 기준점이 될 x,y는 true로 저장합니다.

while문에서, 4가지 방향을 모두 탐색하여 조건에 부합할 블록들을 찾습니다.

이 때 arr가 color일 때에는 visit만 true, arr가 0일 때에는(무지개) tempVisit만 true로 저장합니다.

모든 bfs가 마치면 list에 기준점이 될 x,y와 temp, tempRainbow, tempVisit을 넣습니다.

 

 

Collections.sort(list, new Comparator<Block>() {
    @Override
    public int compare(Block o1, Block o2) {
        if(o1.sum == o2.sum){
            if(o1.rainbow == o2.rainbow){
                if(o1.x == o2.x){
                    return o2.y - o1.y;
                }
                return o2.x - o1.x;
            }
            return o2.rainbow - o1.rainbow;
        }
        return o2.sum - o1.sum;
    }
});//list를 sum, rainbow, x, y에 맞게 내림차순 정렬

그러고 나서 list를 정렬합니다.

sum, rainbow, x, y순으로 우선순의를 매겨 내림차순으로 정렬합니다.

정렬을 모두 마치고 나온 제일 첫 번째 값이 바로 우리가 사용할 인근 영역과 기준점, 블록 개수를 담은 객체입니다.

따라서 list의 0번째 블록 값이 무지개와 같거나 2보다 적거나 list가 0이면 break하여 빠져나옵니다.

그렇지 않을 경우 visit2에 영역의 v를 clone하시고 answer에는 블록 개수의 제곱을 더합니다.

이후 영역의 블록들은 모두 -2(공백)으로 만들어 버립니다. (0은 무지개 블록이기 때문에)

이제 중력이 작용합니다.

gravity()함수는 다음과 같습니다.

static void gravity(){
    //중력 적용은 밑에서 부터 탐색하여 위에서 내려올 것이 있으면 그대로 밑으로보냄
    for(int i = n - 1; i > 0; i--){
        for(int j = 0; j < n; j++){
            if(arr[i][j] == -2){
                int nx = i;
                Queue<Integer> temp = new LinkedList<>();
                for(int t = i; t >= 0; t--){
                    if(arr[t][j] == -1)
                        break;
                    if(arr[t][j] >= 0) {
                        temp.add(arr[t][j]);
                        nx = t;
                        break;
                    }//내려올 블록을 찾았으면 temp에 일단 넣고 nx에 인덱스 저장
                }
                if(temp.size() > 0) {
                    arr[i][j] = temp.poll();
                    arr[nx][j] = -2;
                }//내려올 블록이 있다면 기존 arr에 temp를 넣고 위의 인덱스는 -2넣음(temp안쓰고 변수에 담아서 저장해도됨)
            }
        }
    }
}

중력을 구현할 때에는 반드시 아래에서부터 값을 이동시켜야 합니다.

-1이면 움직일 수 없으니 break하시고 0보다 크거나 같은 값을 찾았다면 값을 저장하여 서로 스위칭한다음 기존 값은 -2(공백)을 넣습니다.

 

for(int i = n - 1; i >= 0; i--)
    for(int j = 0; j < n; j++)
        qq.offer(arr[j][i]);
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        arr[i][j] = qq.poll();
//반시계방향으로 90도 회전
gravity(); //중력 작용

이후 90도 방향으로 반시계 방향 회전하기 위해 qq라는 배열을 선언하여 값을 임의로 받아와서 arr에 다시 삽입합니다.

배열 회전할 때 2중 for문 하나만 써서도 가능한데 전 별로 와닿지 않고 외우는걸 잘 못해서 보통은 자료구조로 구현하는 편입니다. (내 시간 복잡도 어쩔)

이후 또 gavity() 쓰시면 1차례 loop가 끝나겠군요.

이 탐색을 break할 때까지 계속 해주시고 answer출력해주시면 정답이 된답니다.

 

후 삼성 빡구현문제 제가 방금 한 개 더 풀었는데 이건 하루가 넘게 걸렸어요

280줄 써서 구현했는데 어제 풀다가 반례가 자꾸 안되서 접고 오늘 다시 하니까 되긴 한데 이게 시간이 너무 많이 잡아먹혀서 이걸 2,3시간 안에 구현하는 사람들 좀... 존경합니다.

아무리 골드1이라도 그렇지 솔직히 네? 이렇게 까다로울 필요가 있나요 ㅠㅠ

풀긴 풀었는데 음.. 나중에 시간나면 리뷰하겠습니다.

그럼 20000