백준 21610 마법사 상어와 비바라기 - 삼성 SW 역량 테스트 기출

백준 21610 마법사 상어와 비바라기  - 삼성 SW 역량 테스트 기출

1. 문제 링크

 

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

21610번: 마법사 상어와 비바라기

 

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

1. 구름을 담는 리스트를 만들어 구름의 위치를 계속 확인했다.

2. input은 (1, 1)에서 시작하여 (N, N)으로 끝나는 2차원 배열이기 때문에 위치 보정이 필요하다.(선택 사항)

3. 격자는 0행과 N행 0열과 N열이 연결되어 있다. 따라서 좌표상 범위를 벗어나도 격자 안에 위치해야한다.

4. 또한, 이동거리(속도)에 의해 격자를 몇 바퀴 도는 상황을 방지해야한다.

   . 다음 위치 = 현재 위치 + 방향 * 이동거리(속도) % 행 혹은 열의 길이

   . next = now + dir * speed % N

   . 이를 통해 next의 범위는 -N < next < 2N 이 되고 next의 값에 따라 위치 보정을 해준다.

      . next가 음수인 경우 --> next = N - next

      . next가 N보다 크거나 같을 경우 --> next = next - N

5. 물복사가 될 때, 물복사 된 위치와 양을 history에 저장한 후, 원래 격자에 더해줬다.

 

3. 코드

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

public class Main {

	static class Cloud {
		int y, x;

		public Cloud(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}

	static class Move {
		int d, s;

		public Move(int d, int s) {
			super();
			this.d = d;
			this.s = s;
		}

	}

	static class WaterPlus {
		int y, x, plus;

		public WaterPlus(int y, int x, int plus) {
			super();
			this.y = y;
			this.x = x;
			this.plus = plus;
		}

	}

	static int[][] board;
	static int[][] copyBoard;
	static ArrayList<Cloud> cloudList = new ArrayList<>();
	static boolean[][] dead;
	static ArrayList<Move> command = new ArrayList<>();
	static int N, M;
	// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
	static int[] dirY = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int[] dirX = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] bugY = { 1, 1, -1, -1 };
	static int[] bugX = { 1, -1, 1, -1 };
	static int answer = 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\\삼성기출\\마법사상어와비바라기_21610\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);

		board = new int[N][N];

		// 초기 구름 위치 (보정 필요)
		cloudList.add(new Cloud(N - 1, 0));
		cloudList.add(new Cloud(N - 1, 1));
		cloudList.add(new Cloud(N - 2, 0));
		cloudList.add(new Cloud(N - 2, 1));

		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]);
			}
		}

		for (int i = 0; i < M; i++) {
			String[] line = br.readLine().split(" ");
			int d = Integer.parseInt(line[0]);
			int s = Integer.parseInt(line[1]);
			command.add(new Move(d, s));
		}

		for (int i = 0; i < command.size(); i++) {
			Move c = command.get(i);
			moveCloud(c);
			rainFall();
			copyWater();
			makeCloud();
		}

		getSum();

		System.out.println(answer);
	}

	public static void getSum() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				answer += board[i][j];
			}
		}
	}

	public static void makeCloud() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] >= 2 && !dead[i][j]) {
					board[i][j] -= 2;
					cloudList.add(new Cloud(i, j));
				}
			}
		}
	}

	public static void copyWater() {
		copyBoard = new int[N][N];
		ArrayList<WaterPlus> history = new ArrayList<>();
		for (int i = 0; i < cloudList.size(); i++) {
			Cloud now = cloudList.get(i);
			int cnt = 0;
			for (int d = 0; d < 4; d++) {
				int yy = now.y + bugY[d];
				int xx = now.x + bugX[d];

				if (yy >= N || xx >= N || yy < 0 || xx < 0 || board[yy][xx] == 0)
					continue;

				cnt++;
			}

			history.add(new WaterPlus(now.y, now.x, cnt));

		}

		for (int i = 0; i < history.size(); i++) {
			WaterPlus now = history.get(i);
			board[now.y][now.x] += now.plus;
		}

		cloudList.clear();

	}

	public static void rainFall() {
		dead = new boolean[N][N];
		for (int i = 0; i < cloudList.size(); i++) {
			Cloud now = cloudList.get(i);
			board[now.y][now.x] += 1;
			dead[now.y][now.x] = true;
		}

	}

	public static void moveCloud(Move m) {
		int d = m.d - 1;
		int s = m.s;
		for (int i = 0; i < cloudList.size(); i++) {
			Cloud now = cloudList.get(i);
			int yy = now.y + dirY[d] * s % N;
			int xx = now.x + dirX[d] * s % N;

			if (yy < 0) {
				yy = N + yy;
			} else if (yy >= N) {
				yy = yy % N;
			}

			if (xx < 0) {
				xx = N + xx;
			} else if (xx >= N) {
				xx = xx % N;
			}

			now.y = yy;
			now.x = xx;
		}

	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 0행과 N행, 0열과 N열 연결이 되어있는 문제가 연속으로 출제되었다.

2. 이동 거리 혹은 속도가 격자의 길이 N을 훨씬 넘는 경우 보정하는 문제 또한 연속 출제되고 있다.

3. 문제에 따라 유연하게 배열을 복사하는 습관을 들이는게 좋을 것 같다

   . 임시 배열에 로직이 적용된 값을 삽입

   . 로직이 끝난 후 원래 배열에 임시 배열 값을 깊은 복사