[백준/JAVA] 20058번: 마법사 상어와 파이어스톰

📖 문제

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

 

 

 

 

💡  풀이 방식

• BFS + 시뮬레이션

 

1. 배열을 시계 방향으로 90도 회전시킨다. (그림 참고)

private static void rotate(int r, int c, int v, int[][] tmp) {	// tmp : 회전 후 값 저장용 배열
    for(int i = 0 ; i < v; i++) {
        for(int j = 0 ; j < v ; j++) {
            tmp[r + i][c + j] = A[r + v - 1 - j][c + i];
        }
    }
}

 

 

2. 주변에 얼음이 2개 이하인 칸에 대해 얼음의 양을 1 제거한다.

private static int[][] melt() {
    int[][] tmp = new int[len][len];
    for(int i = 0 ; i < len ; i++) {
        for(int j = 0 ; j < len ; j++)
            tmp[i][j] = A[i][j];
    }

    for(int i = 0 ; i < len ; i++) {
        for(int j = 0 ; j < len ; j++) {
            if(tmp[i][j] == 0)  continue;

            int cnt = 0;    // 얼음이 있는 칸 수

            for(int d = 0 ; d < 4 ; d++) {
                int nr = i + dr[d];
                int nc = j + dc[d];

                if(inRange(nr,nc) && A[nr][nc] != 0) {
                    cnt++;
                }
            }

            if(cnt < 3) {  // 얼음이 3개 미만이라면, 얼음 양 -1
                tmp[i][j]--;
            }
        }
    }

    return tmp;
}

 

 

3. 남아있는 얼음 A[r][c]의 합을 구한다. (브루트포스)

int sum = 0;
for(int i = 0 ; i < len ; i++) {
    for(int j = 0 ; j < len ; j++) {
        sum += A[i][j];
    }
}
System.out.println(sum);

 

 

4. 가장 큰 덩어리가 차지하는 칸의 개수를 구한다. (BFS)

visited = new boolean[len][len];
for(int i = 0 ; i < len ; i++) {
    for(int j = 0 ; j < len ; j++) {
        if(!visited[i][j] && A[i][j] != 0) {
            max = Math.max(max, bfs(i,j));
        }
    }
}

System.out.println(max);

private static int bfs(int r, int c) {
    int cnt = 1;

    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[] {r, c});

    visited[r][c] = true;

    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int d = 0 ; d < 4 ; d++) {
            int nr = now[0] + dr[d];
            int nc = now[1] + dc[d];

            if(!inRange(nr,nc)) continue;

            if(!visited[nr][nc] && A[nr][nc] != 0) {
                visited[nr][nc] = true;
                q.add(new int[] {nr, nc});
                cnt++;
            }
        }
    }

    return cnt;
}

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    
    static int N,Q;
    static int[][] A;
    static boolean[][] visited;
    static int len;
    static int max = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        
        len = (int)Math.pow(2,N);
        
        // 격자 입력받기
        A = new int[len][len];
        for(int i = 0 ; i < len ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < len ; j++) {
                A[i][j] = Integer.parseInt(st.nextToken()); // 0: 얼음 없음
            }
        }
        
        
        st = new StringTokenizer(br.readLine(), " ");
        while(Q --> 0) {
            int L = Integer.parseInt(st.nextToken());   // 시전한 단계
            A = divide(L);
            A = melt();
        }
        
        // 1. 남아있는 얼음 A[r][c]의 합 구하기 (브루트포스)
        int sum = 0;
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                sum += A[i][j];
            }
        }
        System.out.println(sum);
        
        // 2. 가장 큰 덩어리가 차지하는 칸의 개수 구하기 (BFS)
        visited = new boolean[len][len];
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                if(!visited[i][j] && A[i][j] != 0) {
                    max = Math.max(max, bfs(i,j));
                }
            }
        }
        
        System.out.println(max);
    }
    
    private static int[][] divide(int num) {
        int[][] tmp = new int[len][len];
        
        // 1) 2^L * 2^L 크기의 부분 격자로 나누기
        int tmpLen = (int)Math.pow(2,num);
        
        for(int i = 0 ; i < len ; i += tmpLen) {
            for(int j = 0 ; j < len ; j += tmpLen) {
                // 2) 모든 부분 격자를 시계 방향으로 90도 회전하기
                rotate(i, j, tmpLen, tmp);
            }
        }
        
        return tmp;
    }
    
    // 💥 시계 방향 90도 회전하는 메소드
    private static void rotate(int r, int c, int v, int[][] tmp) {
        for(int i = 0 ; i < v; i++) {
            for(int j = 0 ; j < v ; j++) {
                tmp[r + i][c + j] = A[r + v - 1 - j][c + i];
            }
        }
    }
    
    // 인접한 칸 중 얼음이 있는 칸 3개 이상 있지 않은 칸은 얼음의 양 -1
    private static int[][] melt() {
        int[][] tmp = new int[len][len];
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++)
                tmp[i][j] = A[i][j];
        }
        
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                if(tmp[i][j] == 0)  continue;
                
                int cnt = 0;    // 얼음이 있는 칸 수
                
                for(int d = 0 ; d < 4 ; d++) {
                    int nr = i + dr[d];
                    int nc = j + dc[d];
                    
                    if(inRange(nr,nc) && A[nr][nc] != 0) {
                        cnt++;
                    }
                }
                
                if(cnt < 3) { // 얼음이 3개 미만이라면, 얼음 양 -1
                    tmp[i][j]--;
                }
            }
        }
        
        return tmp;
    }
    
    // 얼음 덩어리가 차지하는 칸의 개수 계산하는 메소드 (BFS)
    private static int bfs(int r, int c) {
        int cnt = 1;
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {r, c});
        
        visited[r][c] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nr = now[0] + dr[d];
                int nc = now[1] + dc[d];
                
                if(!inRange(nr,nc)) continue;
                
                if(!visited[nr][nc] && A[nr][nc] != 0) {
                    visited[nr][nc] = true;
                    q.add(new int[] {nr, nc});
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
    
    private static boolean inRange(int r, int c) {
        return 0 <= r && r < len && 0 <= c && c < len;
    }
}

 

 

➕ 다른 풀이 방식

- 녹인 결과 반영하는 부분이 다르다.

인접한 얼음의 개수가 3개 미만이라면, 리스트에 추가하고, 해당 부분만 원본 배열에서 값을 1 빼줬다.

백준 - 20058 마법사 상어와 파이어스톰(Java)

 

 

- 배열 회전 함수에서 내가 틀렸던 부분 또 찾음!!! 복사를 잘못한 것임 (인덱스 주의)

나는 그냥 A[i][j] = tmp[i][j]; 했는데 그게 아니었던 것임 ✅

for(int i = 0 ; i < v ; i++) {
    for(int j = 0 ; j < v ; j++) {
        A[r + i][c + j] = tmp[i][j];	// 틀렸던 부분
    }
}

 

[백준] 20058 마법사 상어와 파이어스톰 - 자바

---

💦 어려웠던 점

- 회전 메소드를 제대로 구현 안 해서 틀렸다. (구현하면서도 긴가민가하긴 했다)

- 변경된 값을 원본 격자에 반영하려고 했는데 이 과정에서도 제대로 반영이 안 된 듯 하다. 

 

 

🧐 새로 알게 된 내용

- 시계 방향으로 배열을 회전하는 방법

- 격자 안의 값을 변경한 후, 바로 배열에 반영하는 방법

A = divide(L);
A = melt();

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[boj] 백준 20058 마법사 상어와 파이어스톰 (Java) - 시뮬레이션(배열 회전), BFS

 

[백준] 20058번 - 마법사 상어와 파이어스톰 (java)

 

 

- 풀어보면 좋은 문제들

[백준 20058] 마법사 상어와 파이어스톰 (JAVA)