20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
다른 기능들은 그대로 구현하면 되어서 할만했지만, 오른쪽 90도 돌리는 기능에서 인덱스 접근때문에 계속 헤맸다. 손으로 그리면서 각 인덱스가 90도를 회전했을 때, 어떻게 바뀌는지 확인했더니 공식을 구할 수 있었다.
package boj.p20058;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Stream;
public class Main {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static StringTokenizer st = null;
private static StringBuilder sb = null;
/** 격자의 한 변은 2^N의 길이를 가진다 */
private static int N;
/** 총 시전 횟수 */
private static int Q;
/** 각 시전한 단계를 저장하는 배열 */
private static int[] stepList;
/** 한 변의 길이 */
private static int boardLength;
/** 격자 정보 */
private static int[][] board;
/** 돌린 배열 */
private static int[][] rotatedBoard;
/** 상, 하, 좌, 우 */
private static int[] dr = { -1, 1, 0, 0 };
private static int[] dc = { 0, 0, -1, 1 };
/** 남은 얼음의 총 양 */
private static int restIceCount = 0;
/** 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 */
private static int restMaxIceCount = 0;
/**
* 행, 열 위치정보를 저장하는 클래스
*/
private static class Pos {
int row;
int col;
public Pos(int row, int col) {
this.row = row;
this.col = col;
}
}
public static void main(String[] args) throws Exception {
input();
cast();
getRestIceCount();
getRestMaxIceBlock();
print();
}
private static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
// 2^N이 한 변의 길이가 된다.
boardLength = 1 << N;
board = new int[boardLength][boardLength];
for(int i=0; i<boardLength; i++) {
board[i] = Stream.of(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
stepList = new int[Q];
st = new StringTokenizer(br.readLine());
for(int i=0; i<Q; i++) {
stepList[i] = Integer.parseInt(st.nextToken());
}
}
/**
* 마법을 시전하는 함수
*/
private static void cast() {
rotatedBoard = new int[boardLength][boardLength];
for(int step : stepList) {
// 각 단계에 맞게 2^step * 2^step 크기 만큼의 배열을 회전한다.
int rotateLength = 1 << step;
for(int i=0; i<boardLength; i+=rotateLength) {
for(int j=0; j<boardLength; j+=rotateLength) {
// 회전할 부분 격자의 시작(좌상단)
Pos start = new Pos(i, j);
// 회전할 부분 격자의 마지막(우하단)
Pos end = new Pos(i + rotateLength - 1, j + rotateLength - 1);
rotate(start, end, rotateLength);
}
}
// 한 단계를 마친 배열을 원래 배열에 저장한다.
board = rotatedBoard;
// 한 단계 마치고 얼음이 녹는다.
melt();
}
}
/**
* 부분 격자를 돌리는 함수
*
* @param start 시작 위치
* @param end 마지막 위치
* @param rotateLength 부분 격자의 한 변의 길이
*/
private static void rotate(Pos start, Pos end, int rotateLength) {
int startRow = start.row;
int startCol = start.col;
for(int i=0; i<rotateLength; i++) {
for(int j=0; j<rotateLength; j++) {
rotatedBoard[i+startRow][j+startCol] = board[startRow + rotateLength - j - 1][startCol + i];
}
}
}
/**
* 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸의 얼음의 양을 1 줄이는 함수
*/
private static void melt() {
// 녹고 난 후의 격자
int[][] meltedBoard = new int[boardLength][boardLength];
// 기존 격자를 깊은 복사를 해준다.
for(int i=0; i<boardLength; i++) {
meltedBoard[i] = Arrays.copyOf(board[i], boardLength);
}
for(int i=0; i<boardLength; i++) {
for(int j=0; j<boardLength; j++) {
// 근처에 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않다면,
if(isNearGreaterOrEqualThreeIces(i, j) == false) {
// 현재 칸에 얼음이 있을 경우 1을 빼준다.
if(meltedBoard[i][j] > 0) {
meltedBoard[i][j] -= 1;
}
}
}
}
// 녹고 난 후의 격자를 원래 격자에 저장한다.
board = meltedBoard;
}
/**
* 근처에 얼음이 있는 칸이 3칸 이상 있는지 확인하는 함수이다./
*
* @param row 행
* @param col 열
* @return 근처에 얼음이 있는 칸이 3칸 이상 있다면 true, 아니라면 false를 반환
*/
private static boolean isNearGreaterOrEqualThreeIces(int row, int col) {
int iceCount = 0;
for(int i=0; i<4; i++) {
int nr = row + dr[i];
int nc = col + dc[i];
// 격자의 범위를 벗어난다면 다음 위치를 탐색한다.
if(isValidIndex(nr, nc) == false) {
continue;
}
// 얼음이 있다면 카운트를 증가시켜준다.
if(board[nr][nc] > 0) {
iceCount++;
}
}
// 근처에 얼음이 3칸이상 있다면 true, 아니라면 false를 반환한다.
return iceCount >= 3;
}
/**
* 남은 얼음의 총량을 구하는 함수
*/
private static void getRestIceCount() {
for(int i=0; i<boardLength; i++) {
for(int j=0; j<boardLength; j++) {
int curIceCount = board[i][j];
if(curIceCount > 0) {
restIceCount += curIceCount;
}
}
}
}
/**
* 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하는 함수
*/
private static void getRestMaxIceBlock() {
// 방문 저장 배열
boolean[][] isVisited = new boolean[boardLength][boardLength];
Queue<Pos> queue = new ArrayDeque<>();
for(int i=0; i<boardLength; i++) {
for(int j=0; j<boardLength; j++) {
// 이미 방문한 곳이라면 다른곳을 탐색한다.
if(isVisited[i][j] == true) {
continue;
}
// 얼음이 없다면 다른곳을 탐색한다.
if(board[i][j] == 0) {
continue;
}
int count = 0;
// 현재칸을 방문처리 해준다.
isVisited[i][j] = true;
// 큐에 현재칸을 넣어준다.
queue.add(new Pos(i, j));
// BFS
while(!queue.isEmpty()) {
Pos cur = queue.poll();
count++;
for(int d=0; d<4; d++) {
int nr = cur.row + dr[d];
int nc = cur.col + dc[d];
if(isValidIndex(nr, nc) == false) {
continue;
}
if(isVisited[nr][nc] == true) {
continue;
}
// 다음칸이 얼음이 있을경우 큐에 넣어준다.
if(board[nr][nc] > 0) {
isVisited[nr][nc] = true;
queue.add(new Pos(nr, nc));
}
}
}
// 최댓값을 갱신해준다.
restMaxIceCount = Math.max(restMaxIceCount, count);
}
}
}
/**
* 인자로 들어온 위치가 범위를 벗어나지 않는지 확인하는 함수
*
* @param row 행
* @param col 열
* @return 범위를 벗어나지 않는다면 true, 벗어난다면 false를 반환
*/
private static boolean isValidIndex(int row, int col) {
if(row < 0 || row >= boardLength) {
return false;
}
if(col < 0 || col >= boardLength) {
return false;
}
return true;
}
private static void print() throws Exception {
sb = new StringBuilder();
sb.append(restIceCount)
.append("\n")
.append(restMaxIceCount);
bw.write(sb.toString());
bw.flush();
bw.close();
}
}'PS > 백준' 카테고리의 다른 글
| 백준 / 그리디 / 1744번 / 수 묶기 / Java (0) | 2023.11.07 |
|---|---|
| 백준 / 그래프 / 17471번 / 게리맨더링 / Java (1) | 2023.09.02 |
| 백준 / 백트래킹 / 15683번 / 감시 / Java (0) | 2023.07.27 |
| 백준 / 그래프 / 2178번 / 미로 탐색 / JS (0) | 2023.04.28 |