백준 21611 마법사 상어와 블리자드 - 삼성 SW 역량 테스트 기출

백준 21611 마법사 상어와 블리자드  - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

21611번: 마법사 상어와 블리자드

 

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

1. 2차원 배열에서 달팽이처럼 빙글빙글 돈다.

2. 아래의 순서대로 반복한다.

마법 사용 2차원 배열 -> 1차원 배열    반복{       구슬 이동       구슬 폭발 (폭발 없으면 반복 멈춤)    }    구슬 변화 1차원 배열 -> 2차원 배열

3. 2차원 배열을 순회할 때, 달팽이처럼 도는데 다음의 방법으로 순회했다.

   . ←, ↓, →, ↑순으로 방향을 돌며, 이동을 두 번할 때마다 이동거리가 늘어난다.

   . [←↓] >> [→→↑↑] >> [←←←↓↓↓] >>

   . 이동거리는 2번의 이동이 완료될 때 마다 ++ / 방향 전환은 이동이 완료되면

 

4. 구슬이 폭발하거나 변화할 때, 마지막 값까지 적용되었는지 확인이 필요했다.

   . i번째까지 그룹임을 확인하다가 i+1이 값이 다르면 이전 그룹에 대해 로직을 적용했다.

   . 근데 그룹 확인만 하고 로직이 적용이 안 될 수가 있다.(마지막까지 그룹 결성이 될 경우)

   . i가 마지막 인덱스일 때 로직 적용 조건에 맞으면 로직을 적용했다.

3. 코드

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

public class Main {

	static class Magic {
		int d, s;

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

	}

	static class Pair {
		int y, x;

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

	}

	// ↑, ↓, ←, →
	static int[] dirY = { -1, 1, 0, 0 };
	static int[] dirX = { 0, 0, -1, 1 };

	static int[] chainY = { 0, 1, 0, -1 };
	static int[] chainX = { -1, 0, 1, 0 };
	static int[][] board;
	static ArrayList<Magic> commands = new ArrayList<>();
	static ArrayList<Integer> chains;
	static Pair shark;
	static int N, M;
	static int[] balls;
	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\\삼성기출\\마법사상어와블리자드_21611\\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];
		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[] ds = br.readLine().split(" ");
			int d = Integer.parseInt(ds[0]) - 1;
			int s = Integer.parseInt(ds[1]);

			commands.add(new Magic(d, s));
		}

		shark = new Pair(N / 2, N / 2);
		balls = new int[4];

		for (int i = 0; i < commands.size(); i++) {
			doMagic(commands.get(i));
			makeChain();

			boolean go = true;
			while (go) {
				ballMove();
				go = ballBomb();
			}

			ballDivide();
			makeBoard();
		}

		for (int i = 1; i < 4; i++) {
			answer += balls[i] * i;
		}

		System.out.println(answer);
	}

	static void ballDivide() {
		ArrayList<Integer> temp = new ArrayList<>();

		int target = 0;
		int groupCnt = 0;
		for (int i = 0; i < chains.size(); i++) {
			int now = chains.get(i);
			if (target == 0) {
				target = now;
				++groupCnt;
			} else {
				if (target == now) {
					++groupCnt;

				} else {
					temp.add(groupCnt);
					temp.add(target);
					groupCnt = 1;
					target = now;

				}
				if (i == chains.size() - 1) {
					temp.add(groupCnt);
					temp.add(target);
				}
			}
		}
		while (temp.size() > N * N - 1) { // chain의 최대 길이는 N * N - 1
			temp.remove(N * N - 1);
		}

		chains.clear();
		chains.addAll(temp);
	}

	static boolean ballBomb() {

		int target = 0; // 터질 구슬의 번호
		int groupCnt = 0; // 그룹 몇개 들어갔나?
		int groupStart = -1; // 그룹이 시작 번호

		boolean isBomb = false;
		for (int i = 0; i < chains.size(); i++) {
			int now = chains.get(i);
			if (target == 0) { // 초기상태
				target = now;
				++groupCnt;
				groupStart = 0;
			} else {
				if (target == now) {
					++groupCnt;
					if (i == chains.size() - 1 && groupCnt >= 4) { // 마지막까지 4개이상 그룹화되었을 경우 처리
						while (groupCnt-- > 0) {
							++balls[target]; // 구슬 카운트
							chains.set(groupStart++, 0); // 폭파자리는 0으로
						}
						isBomb = true;
					}
				} else {
					if (groupCnt >= 4) { // 폭파
						while (groupCnt-- > 0) {
							++balls[target]; // 구슬 카운트
							chains.set(groupStart++, 0); // 폭파자리는 0으로
						}
						isBomb = true;
					}

					groupCnt = 1;
					groupStart = i;
					target = now;
				}
			}
		}

		return isBomb;
	}

	static void ballMove() {
		ArrayList<Integer> temp = new ArrayList<Integer>();
		for (int i = 0; i < chains.size(); i++) {
			if (chains.get(i) == 0)
				continue;
			temp.add(chains.get(i));
		}
		chains.clear();
		chains.addAll(temp);
	}

	static void makeBoard() {
		int y = shark.y;
		int x = shark.x;
		int loop = 0;
		int len = 1; // 11 22 33 44 순으로 빙글빙글
		int d = 0; // ←, ↓, →, ↑
		int index = 0;
		board = new int[N][N];
		boolean go = true;
		if (chains.isEmpty()) {
			return;
		}
		while (true) {
			for (int i = 0; i < len; i++) {
				int yy = y + chainY[d];
				int xx = x + chainX[d];

				if (yy >= N || xx >= N || yy < 0 || xx < 0) {
					go = false;
					break;
				}
				board[yy][xx] = chains.get(index);

				if (++index >= chains.size()) {
					go = false;
					break;
				}

				y = yy;
				x = xx;

			}
			if (!go)
				break;

			++loop;

			if (loop == 2) {
				loop = 0;
				++len;
			}

			d += 1;
			d %= 4;

		}
	}

	static void makeChain() {
		chains = new ArrayList<>();
		int y = shark.y;
		int x = shark.x;
		int loop = 0;
		int len = 1; // 11 22 33 44 순으로 빙글빙글
		int d = 0; // ←, ↓, →, ↑

		boolean go = true;
		while (true) {
			for (int i = 0; i < len; i++) {
				int yy = y + chainY[d];
				int xx = x + chainX[d];

				if (yy >= N || xx >= N || yy < 0 || xx < 0) {
					go = false;
					break;
				}
				if (board[yy][xx] != 0)
					chains.add(board[yy][xx]);

				y = yy;
				x = xx;

			}
			if (!go)
				break;

			++loop;

			if (loop == 2) {
				loop = 0;
				++len;
			}

			d += 1;
			d %= 4;

		}
	}

	static void doMagic(Magic m) {
		int d = m.d;
		int s = m.s;
		int x = shark.x;
		int y = shark.y;
		for (int i = 0; i < s; i++) {
			int yy = y + dirY[d];
			int xx = x + dirX[d];

			if (yy >= N || xx >= N || yy < 0 || xx < 0)
				break;

			board[yy][xx] = 0;
			y = yy;
			x = xx;
		}
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 달팽이 순회는 이전에 했던 경험이 있어서 어렵지 않았다.

2. 구슬 폭발, 변화에서 마지막 인덱스가 처리하지 못 했었다.(디테일 검토 필요)

3. 2차원 -> 1차원으로 한 뒤에 다시 2차원으로 돌려야하나 했는데 마법 때문에 다시 2차원으로 돌려야했다.