백준 20058 마법사 상어와 파이어스톰 - 삼성 SW 역량 테스트 기출

백준 20058 마법사 상어와 파이어스톰  - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

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

 

2. 문제 해결에 대한 아이디어

• 격자에 대한 반시계 방향 회전이 가장 어려웠다.
• 격자를 부분 격자로 나누어 각 부분 격자를 반시계 방향으로 돌리는 것이기 때문에 위치 보정이 힘들었다.
• 차라리 각 부분 격자를 돌리고나서 그 값을 격자에 넣는 것이 더 쉬울 것이다.(이렇게 안 함)
• 위치에 대한 보정을 할 땐, 종이에 직접 작성해보는 것이 이해하기 쉽다.
• 얼음이 녹은 상황을 임시 배열에 저장해두고 나중에 원래 배열로 복사했다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	static int N, Q;
	static int[][] board;
	static int[][] copyBoard;
	static boolean[][] visit;
	static ArrayList<Integer> command = new ArrayList<>();
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int L = 0;

	static int sum = 0;
	static int size = 0;
	static int tempCnt = 0;

	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\마법사상어와파이어스톰_20058\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nq = br.readLine().split(" ");
		N = Integer.parseInt(nq[0]);
		Q = Integer.parseInt(nq[1]);

		N = (int) Math.pow(2, N);

		board = new int[N][N];
		visit = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
			}
		}

		String[] line = br.readLine().split(" ");
		for (int i = 0; i < Q; i++) {
			command.add(Integer.parseInt(line[i]));
		}

		for (int i = 0; i < command.size(); i++) {
			L = (int) Math.pow(2, command.get(i));
			rotate();
			melt();
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] != 0) {
					sum += board[i][j];
					visit = new boolean[N][N];
					checkSize(i, j);
					size = Math.max(tempCnt, size);
					tempCnt = 0;
				}

			}
		}

		System.out.println(sum);
		System.out.println(size);

	}

	static void checkSize(int i, int j) {
		visit[i][j] = true;
		tempCnt++;
		for (int d = 0; d < 4; d++) {
			int ii = i + dirY[d];
			int jj = j + dirX[d];

			if (ii >= N || jj >= N || ii < 0 || jj < 0 || visit[ii][jj] || board[ii][jj] == 0)
				continue;

			checkSize(ii, jj);
		}
	}

	static void copy() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = copyBoard[i][j];
			}
		}
	}

	static void melt() {
		copyBoard = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] != 0) {
					int cnt = 0;
					for (int d = 0; d < 4; d++) {
						int ii = i + dirY[d];
						int jj = j + dirX[d];

						if (ii >= N || jj >= N || ii < 0 || jj < 0 || board[ii][jj] == 0)
							continue;
						++cnt;
					}
					if (cnt < 3)
						copyBoard[i][j] = board[i][j] - 1;
					else
						copyBoard[i][j] = board[i][j];
				}
			}
		}
		copy();
	}

	static void rotate() {
		copyBoard = new int[N][N];
		int startI = 0;
		int endI = L;
		int startJ = 0;
		int endJ = L;
		while (endI <= N) {
			for (int i = startI; i < endI; i++) {
				for (int j = startJ; j < endJ; j++) {
					copyBoard[j - startJ + startI][endJ - 1 - i + startI] = board[i][j];
				}
			}
			startJ += L;
			endJ += L;
			if (endJ > N) {
				startI += L;
				endI += L;
				startJ = 0;
				endJ = L;
			}
		}
		copy();
	}
}

 

4. 채점 결과

 

5. 느낀 점

• 부분 배열마다 회전을 해야하는 경우, 각각 회전한 다음에 전체 배열에 넣는게 더 쉽다.
• 얼음이 녹은 위치를 따로 저장해두고 원래 배열을 수정하는 것도 괜찮을 것 같다.
• 얼음덩이에 대한 크기를 체크할 때, 좌표를 갖는 클래스를 만들어 큐에 넣고 돌리려고 했다. (통과 되긴함)
• 하지만 재귀로 하니까 수행시간이 반으로 줄어들어 재귀로 구현했다.