🔍 문제
💻 제출
📌 입력
📌 출력
📌 제한
🤔 생각
해당 문제를 읽었을때 단계를 나누어서 풀어야 할 것 같다고 생각이 들었다.
- L값에 따라 영역을 분류 하기
- 분류한 영역을 rotate 하면서 값 변동 하기
- 인접한 얼음 영역이 2개 이하면 해당 영역 값 줄여주기
- 주어진 Q값에 따라 1 ~ 3을 반복 하기
📝 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, Q;
static int[] L;
static int[][] map;
static int[] dx = {0, 1, 0, -1}; //동 남 서 북 x좌표
static int[] dy = {1, 0, -1, 0}; //동 남 서 북 y좌표
static boolean[][] visited;
static long maxIce = 0;
static long maxLand = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken()); //N
Q = Integer.parseInt(st.nextToken()); //시전 횟수
N = (int)Math.pow(2,N);
map = new int[N][N];
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(stD.nextToken());
}
}
L = new int[Q];
StringTokenizer stL = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < Q; i++) {
L[i] = Integer.parseInt(stL.nextToken());
}
for (int i = 0; i < Q; i++) {
map = divide(L[i]);
map = melt();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
maxIce += map[i][j];
if (map[i][j] != 0 && visited[i][j] == false){ //얼음 영역 이라면
bfs(i,j);
}
}
}
bw.write(maxIce + "\n");
bw.write(maxLand + "\n");
bw.flush();
bw.close();
}
static int[][] divide(int l) { //구역을 나누기
int[][] replaceArea = new int[N][N];
int powL = (int) Math.pow(2, l); // 2^l 으로 제곱 연산
for (int i = 0; i < N; i += powL) {
for (int j = 0; j < N; j += powL) {
rotateIce(i, j, powL, replaceArea);
}
}
return replaceArea;
}
static void rotateIce(int x, int y, int powL, int[][] replaceArea) {
for (int i = 0; i < powL; i++) {
for (int j = 0; j < powL; j++) {
replaceArea[j + x][powL - 1 - i + y] = map[x + i][y + j];
}
}
}
static int[][] melt() {
int[][] replaceArea = new int[N][N];
for (int i = 0; i < N; i++) {
replaceArea[i] = Arrays.copyOf(map[i], N);
}
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
int cnt = 0;
if (map[x][y] == 0) {
continue; //이미 얼음이 다녹은 칸
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
if (map[nx][ny] > 0) {
cnt++; //얼음이 주변에 있음
}
}
}
if (cnt < 3) {
replaceArea[x][y]--; //임시 배열 얼음 값 감소
//주변 3면 이상이 얼음 영역 아님
}
}
}
return replaceArea;
}
static void bfs(int x,int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {x,y});
visited[x][y] = true;
long land = 1;
while (!q.isEmpty()){
int[] now = q.poll();
for (int i=0; i<4; i++){
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
if (visited[nx][ny] == false && map[nx][ny] > 0){
land++;
visited[nx][ny] = true;
q.offer(new int[] {nx,ny});
}
}
}
}
maxLand = Math.max(land,maxLand);
}
}📑 영역 분리
L = new int[Q];
StringTokenizer stL = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < Q; i++) {
L[i] = Integer.parseInt(stL.nextToken());
}
for (int i = 0; i < Q; i++) {
map = divide(L[i]);
map = melt();
}
static int[][] divide(int l) { //구역을 나누기
int[][] replaceArea = new int[N][N];
int powL = (int) Math.pow(2, l); // 2^l 으로 제곱 연산
for (int i = 0; i < N; i += powL) {
for (int j = 0; j < N; j += powL) {
rotateIce(i, j, powL, replaceArea);
}
}
return replaceArea;
}L값이 오름차순으로 진행 되는 것이 아니라 주어진 입력값에 따라 다르게 적용 되야 하므로 배열에 저장 후 반복문을 divide 함수를 호출 한다.
주어진 L값을 제곱 연산 하고 반복문 i,j를 제곱 연산 값만큼 증가 시켜 주면 영역을 분리 할 수 있다.
분리한 영역의 첫번째 좌표 값을 기준으로 rotateIce 함수가 호출 된다.
📑 회전
static void rotateIce(int x, int y, int powL, int[][] replaceArea) {
for (int i = 0; i < powL; i++) {
for (int j = 0; j < powL; j++) {
replaceArea[j + x][powL - 1 - i + y] = map[x + i][y + j];
}
}
}
한번에 회전을 해야 하기 때문에 임시 배열인 replace를 생성 해줬으며 replace의 x 와 map 의 y값은 동일한 규칙을 확인 할 수 있다.
replace 의 y 값은 주어진 L의 제곱 값 - i - 1 연산으로 구할 수 있다.
이후 영역의 첫번째 값을 각 좌표에 전부 더해주면
replaceArea[j + x][powL - 1 - i + y] = map[x + i][y + j];를 얻을 수 있다.
📑 얼음 녹이기
static int[][] melt() {
int[][] replaceArea = new int[N][N];
for (int i = 0; i < N; i++) {
replaceArea[i] = Arrays.copyOf(map[i], N);
}
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
int cnt = 0;
if (map[x][y] == 0) {
continue; //이미 얼음이 다녹은 칸
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
if (map[nx][ny] > 0) {
cnt++; //얼음이 주변에 있음
}
}
}
if (cnt < 3) {
replaceArea[x][y]--; //임시 배열 얼음 값 감소
//주변 3면 이상이 얼음 영역 아님
}
}
}
return replaceArea;
}
모든 영역을 상 하 좌 우 이동하면서 인접 영역을 탐색한다.
주변에 얼음 수가 2개 이하라면 현재 영역의 값을 줄여주며 진행 하면 된다.
📑 가장 큰 덩어리 값 계산
static void bfs(int x,int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {x,y});
visited[x][y] = true;
long land = 1;
while (!q.isEmpty()){
int[] now = q.poll();
for (int i=0; i<4; i++){
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
if (visited[nx][ny] == false && map[nx][ny] > 0){
land++;
visited[nx][ny] = true;
q.offer(new int[] {nx,ny});
}
}
}
}
maxLand = Math.max(land,maxLand);
}bfs로 탐색 하여 연결된 영역 얼음 합산의 가장 큰 값을 구한다.
📗 정리
현재까지 풀었던 문제 중에서 가장 어렵다고 느껴졌다.
이상하게 rotate 함수를 구현 할 때 공식을 찾지 못해서 많은 시간을 허비 했다.
전부 구현 하고 다시 돌아봤을 때는 어려운 문제가 아니라고 생각이 드는데 풀이 당시에는 왜 그렇게 생각이 안 났는지 모르겠다.
수학 문제를 푼 지 한참 지나서 머리가 굳어버린 것 일지도.
문제에 표시되는 티어가 높아 질 수록 풀이 단계가 점점 많아지지만 분리 해서 구현 해나가다 보면 난해 하지는 않은 것 같다.
wkd86591247@gmail.com