[BOJ - JAVA] (삼성전자 기출) 20058 - 마법사 상어와 파이어스톰 (회전, 구현, 시뮬레이션, BFS)

# 주소

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

20058번: 마법사 상어와 파이어스톰

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
class M{
    static int n, q;
    static int size;
    static int[][] arr;
    static boolean[][] visit;
    static ArrayList<Integer> list = new ArrayList<>();
    static Queue<Point> queue = new LinkedList<>();
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    static int answer = 0;
    static int sum = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        q = scan.nextInt();
        size = (int)Math.pow(2, n);
        arr = new int[size][size];
        visit = new boolean[size][size];
        for(int i = 0; i < size; i++)
            for(int j = 0; j < size; j++)
                arr[i][j] = scan.nextInt();
        //n과 q와 arr까지 입력받음
        for(int i = 0; i < q; i++)
            list.add(scan.nextInt());
        //파이어스톰 시킬 값을 list에 입력받음
        int index = 0;
        while (index < q) {
            int now = (int) Math.pow(2, list.get(index));
            for (int i = 0; i < size; i += now)
                for (int j = 0; j < size; j += now)
                    rotate(i, j, i + now, j + now);
            //배열 회전
            int[][] map = new int[size][size];
            for(int i = 0; i < size; i++)
                System.arraycopy(arr[i], 0, map[i], 0, size);
            //map배열에 arr를 깊은 복사
            for(int i = 0; i < size; i++){
                for(int j = 0; j < size; j++){
                    int count = 0;
                    if(map[i][j] == 0)
                        continue;
                    for(int k = 0; k < 4; k++){
                        int nx = i + dir[k][0];
                        int ny = j + dir[k][1];
                        if(nx < 0 || ny < 0 || nx >= size || ny >= size || map[nx][ny] == 0)
                            count++;
                    }
                    if(count >= 2)
                        arr[i][j]--;
                    if(arr[i][j] < 0)
                        arr[i][j] = 0;
                }
            }
            //배열을 전체 탐색하면서 인접한 얼음이 2이하인 요소는 arr값 감소(얼음 감소)
            index++;
        }
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                if(!visit[i][j] && arr[i][j] > 0){
                    sum += arr[i][j];
                    queue.offer(new Point(i, j));
                    visit[i][j] = true;
                    bfs();
                }
            }
        }
        //얼음의 크기를 구하기 위해 bfs탐색
        System.out.println(sum);
        System.out.println(answer);
    }
    static void rotate(int x, int y, int X, int Y){
        Queue<Integer> queue = new LinkedList<>();
        for(int i = x; i < X; i++)
            for(int j = y; j < Y; j++)
                queue.offer(arr[i][j]);
        for(int i = Y - 1; i >= y; i--)
            for(int j = x; j < X; j++)
                arr[j][i] = queue.poll();
    }//배열을 시계방향으로 90도 회전
    static void bfs(){
        int t = 1;
        while (!queue.isEmpty()){
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                //4방향 탐색을 위한 for문
                if(nx < 0 || ny < 0 || nx >= size || ny >= size)
                    continue;
                if(arr[nx][ny] == 0)
                    continue;
                if(visit[nx][ny])
                    continue;
                queue.offer(new Point(nx, ny));
                visit[nx][ny] = true;
                t++;
                sum += arr[nx][ny];
            }
        }
        answer = Math.max(t, answer);
        //bfs탐색을 통한 인접한 얼음 모두탐색
    }
}

이번엔 구현 문제 중에서 꽤 쉬운 문제로 가져왔습니다.

배열을 90도로 회전 시키는 부분과 BFS만 잘 인지하고 계셔도 푸는데 전혀 무리 없을 것입니다.

같이 살펴봅시다.

# 문제 요약

1. 배열의 값은 arr에, 2의 r제곱이 될 값은 list에 담는다.

2. 이후 list에서 뽑아온 2의 r제곱값에 대해, 배열의 처음부터 끝인덱스까지 정사각형 형태로 부분 격자를 나누어 회전한다.

3. 임시 배열인 map을 만들어 인접한 얼음의 수에 따라 arr값을 감소시킨다. (깊은 복사)

4. 이후 bfs를 이용하여 (혹은 dfs) 인접한 최대의 얼음의 양을 구하고 합도 구한다.

static int n, q;
static int size;
static int[][] arr;
static boolean[][] visit;
static ArrayList<Integer> list = new ArrayList<>();
static Queue<Point> queue = new LinkedList<>();
static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
static int answer = 0;
static int sum = 0;

최초의 static으로 선언할 것들은 조금 많습니다.

answer는 얼음의 개수, sum은 얼음의 총합입니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
q = scan.nextInt();
size = (int)Math.pow(2, n);
arr = new int[size][size];
visit = new boolean[size][size];
for(int i = 0; i < size; i++)
    for(int j = 0; j < size; j++)
        arr[i][j] = scan.nextInt();

최초의 입력문입니다.

저는 size를 그냥 2의 n제곱으로 나타내서 썼는데, 2의 n제곱을 쓸 일이 많기 때문에 size로 선언하고 쓰시는 것이 좋습니다.

arr의 크기와 visit의 크기가 모두 size by size이기 때문이기도 합니다.

이후 2중 for문을 이용하여 arr값을 입력받습니다.

for(int i = 0; i < q; i++)
    list.add(scan.nextInt());

list에는 q개의 값을 입력받아, 앞으로 쓰일 파이어스톰값을 저장합니다.

int index = 0;
while (index < q) {
    int now = (int) Math.pow(2, list.get(index));
    for (int i = 0; i < size; i += now)
        for (int j = 0; j < size; j += now)
            rotate(i, j, i + now, j + now);

이후, while문을 이용하여 q번동안 얼음의 양을 조정합니다.

제일 먼저 배열을 회전시키기 위해 2중 for문을 이용하여 i,j 부터 i + now, j + now까지 회전할텐데요.

static void rotate(int x, int y, int X, int Y){
    Queue<Integer> queue = new LinkedList<>();
    for(int i = x; i < X; i++)
        for(int j = y; j < Y; j++)
            queue.offer(arr[i][j]);
    for(int i = Y - 1; i >= y; i--)
        for(int j = x; j < X; j++)
            arr[j][i] = queue.poll();
}//배열을 시계방향으로 90도 회전

90도 회전은 다음과 같습니다.

전 좀 무식한 방법으로 배열 회전을 하는 편인데요.

언뜻보기에 뭔소리야? 싶지만, 90도 시계방향 회전은 이 7줄이면 뭐든지 다 할 수 있습니다.

특히 3번째 줄과 7번째 줄은 항상 같고 4번째 줄과 6번째 줄은 6번째줄을 서로 뒤집으면 끝납니다.

그렇담 반시계방향일때에는? 

그 때에는 4번재 줄과 6번째 줄이 항상 같고 3번째 줄과 7번째 줄은, 7번째 줄을 뒤집은 모양입니다.

신기하죠? 그래서 전 그냥 외워서 구현해오고 있습니다.

2중 for문 한 개로 구현하셔서 멋있게도 할 수 있는데 전 그 방식이 너무 안외워지더라구요...

그래서 queue에 값을 다 저장하고 90도 돌린 형태에서 값을 순차적으로 뿌리는 형식을 취하고 있습니다.

 

이후부터가 중요합니다.

int[][] map = new int[size][size];
for(int i = 0; i < size; i++)
    System.arraycopy(arr[i], 0, map[i], 0, size);
//map배열에 arr를 깊은 복사

map이라는 임시 2차원 배열을 만들어, arr를 깊은 복사 합니다.

깊은 복사를 하게되면 arr값이 바뀌어도 map은 그대로 자기만의 값을 가지기 때문에 얕은 복사인지, 깊은 복사인지에 따라 문제 풀이가 천차만별이 될 수 있으니 잘 기억해두셔야합니다.

System.arraycopy를 이용한다던지, arr.clone을 하시면 깊은 복사가 되는데에 반해

map = arr 이렇게 사용하시면 얕은 복사가 되기 때문에 주의하셔야겠습니다.

전 처음에 배열 복사를 rotate하기 전에 했다가 정답이 예제4번만 안되길래 음 뭐지 이랬는데 알고봤더니 회전하기도 전에 map에 복사했더라고요 ㅋㅋ.

그렇게되면 엉망진창이 되기 땜에 순서 조심하셔야겠습니다..

for(int i = 0; i < size; i++){
    for(int j = 0; j < size; j++){
        int count = 0;
        if(map[i][j] == 0)
            continue;
        for(int k = 0; k < 4; k++){
            int nx = i + dir[k][0];
            int ny = j + dir[k][1];
            if(nx < 0 || ny < 0 || nx >= size || ny >= size || map[nx][ny] == 0)
                count++;
        }
        if(count >= 2)
            arr[i][j]--;
        if(arr[i][j] < 0)
            arr[i][j] = 0;
    }
}

이젠 정말 쉽습니다.

4방향을 모두 탐색하여 배열 요소를 벗어나거나 옆에 얼음이 없으면 count를 증가합니다.

이 때 count가 2이상이면 arr값을 감소시킵니다. 혹시 몰라 arr값이 0보다 작아지면 arr는 0이 되는 것도 추가는 했습니다.

그리고 인접한 값을 찾을 때 이 때 깊은 복사를 한 이유가 나오게 됩니다.

arr를 이용하여 인접한 얼음을 탐색하게 되면, 얼음이 문제에서 나와있다시피 동시에 녹기 때문에 만약 arr값이 0이되는 지점이 존재한다면 그 다음의 인덱스에서 분명 영향을 받아 arr값이 감소안해도 될 때 감소될 수가 있게 됩니다.

그러니 그러지말고, map이라는 가상의 배열을 복사해둔 뒤 map을 가지고 주변 얼음을 탐색하면서 0이면 map대신 arr를 감소하시면 되겠습니다. 

이해안되시면 반복해서 읽어보세요.

for(int i = 0; i < size; i++){
    for(int j = 0; j < size; j++){
        if(!visit[i][j] && arr[i][j] > 0){
            sum += arr[i][j];
            queue.offer(new Point(i, j));
            visit[i][j] = true;
            bfs();
        }
    }
}

그러고 난 뒤 arr가 1이상이고 방문하지 않은 값부터 모조리 bfs방법으로 찾아낼텐데요.

만약 모든 얼음이 0보다 크다면 최초의 bfs 1회 실행으로 모든 얼음을 탐색하게 될테니 여기서의 제어문이 2번 이상 실행될 일 없이 바로 종료될 수도 있습니다.

bfs는 이러한 묘한 매력을 가지고 있습니다. 왜 그런지 bfs내부를 보겠습니다

static void bfs(){
    int t = 1;
    while (!queue.isEmpty()){
        Point now = queue.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            //4방향 탐색을 위한 for문
            if(nx < 0 || ny < 0 || nx >= size || ny >= size)
                continue;
            if(arr[nx][ny] == 0)
                continue;
            if(visit[nx][ny])
                continue;
            queue.offer(new Point(nx, ny));
            visit[nx][ny] = true;
            t++;
            sum += arr[nx][ny];
        }
    }
    answer = Math.max(t, answer);
    //bfs탐색을 통한 인접한 얼음 모두탐색

바로 이러한 이유 때문입니다.

4번의 for문으로 주변을 탐색했을 때 얼음이 있으면 ok하고 옆 인덱스로 넘어가, queue에 담고 visit도 true로 만들게 됩니다.

그러나 배열의 인덱스를 벗어나거나 arr값이 0인 지점이거나 방문한 지점이면 continue하여 queue에 들어갈 값들은 오직 1이상의 얼음인 것들만 들어갈 수 있게 잘 짜셔야 합니다.

마찬가지로 queue에 담을 수 있다는 것은 새로운 얼음인덱스를 의미하기 때문에 visit을 true로 바꾸고 t도 증가, sum에도 얼음의 값을 넣어서 갱신합니다.

제일 위에 보시면 while문이 있는걸 보실 수 있는데, 만약 얼음을 모두 탐색하고 난다면 queue에 더 이상 남은 값이 없기 때문에 종료가 될텐데요.

그럼 그 때의 t와 answer를 비교하여, 큰 값을 answer에 담으며 bfs는 종료됩니다.

이 answer가 정답이 될 얼음의 양을 의미하고 sum은 얼음의 총합을 의미하게 된답니다.

 

이번엔 조금 쉬운 문제로 리뷰를 하니 맘이 편해지네요... 감사합니다.