본문 바로가기
Algorithm/백준

[백준] 21611번 - 마법사 상어와 블리자드 (Java)

728x90

 

 

 

반응형

 

 


 문제

 

 

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

 

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

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (

www.acmicpc.net

 

 

 


 풀이

 

삼성 SW 역량 테스트 기출 문제이다.

 

구현량이 많은 시뮬레이션 문제라 풀다가 토나올 뻔 했다...

 

입력은 2차원 배열이지만 달팽이 모양을 일렬로 펼쳐 1차원으로 생각하고 풀었다.

 

프로그램 전체 로직은 다음과 같다. 

 

1. 처음에 달팽이 모양으로 input을 탐색하여 map을 1차원 배열로 저장한다.

2. 4방향의 블리자드 인덱스들을 2차원 배열(bzIdx)로 계산해둔다.

3. bzIdx를 참고해 d방향의 s개 만큼의 인덱스들을 map에서 0으로 바꿔준다.

4. 1차원 map을 왼쪽으로 밀어준다.

5. 연속 4개 이상의 구슬들을 터뜨리고 왼쪽으로 밀어준다. 터뜨린 개수는 marble 배열로 관리한다. 

6. 5를 더 이상 터뜨린 구슬이 없을 때 까지 반복한다.

7. 구슬을 변화시킨다.

8. 3~7을 m번 반복한다.

 

 

 


 코드

 

import java.util.*;
import java.io.*;

public class Main {

	static int n, map[], marble[];
	static int[] dr = { 1, 0, -1, 0 }; // 하, 우, 상, 좌
	static int[] dc = { 0, 1, 0, -1 };
	static int[][] bzIdx; // 블리자드 각 방향별 인덱스 좌, 하, 상, 우
	static int[] bzConvert = { 0, 3, 1, 0, 2 }; // 입력값 d를 알맞게 변환 ex) d=1 -> bzConvert[1]=3 -> bzIdx[3] 참조

	/****************** Main ******************/
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] input = new int[n][n];

		map = new int[n * n];
		marble = new int[4];
		bzIdx = new int[4][n / 2];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++)
				input[i][j] = Integer.parseInt(st.nextToken());
		}

		makeBzIdx(); // 블리자드 각 방향별로 1차원에서의 인덱스 생성
		to1D(input); // 2차원 입력을 1차원 map으로 변환

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());

			blizzard(bzConvert[d], s); // 블리자드 마법
			move(); // 구슬 이동

			// 터뜨릴거 없을 때 까지 구슬 폭발
			while (bomb()) {}

			change(); // 구슬 변화
		}
		System.out.println(1 * marble[1] + 2 * marble[2] + 3 * marble[3]);
	}
	/****************** Main End ******************/

	
	
	/****************** Method ******************/

	// makeBzIdx: 1차원 map에서 블리자드 쏠 수 있게 인덱스 생성 (왼쪽, 아래, 오른쪽, 위 순)
	// ex) 왼쪽: 1, 10, 27 ..., 아래: 3, 14, 33...
	static void makeBzIdx() {
		int cnt = 1;
		int level = 1;
		for (int j = 0; j < (n / 2) / 1; j++) {
			for (int i = 0; i < 4; i++) {
				bzIdx[i][j] = cnt;

				if (i == 3)
					cnt += 2 * level + 1;
				else
					cnt += level * 2;
			}
			level++;
		}
	}

	// to1D: 2차원 input을 달팽이 모양으로 탐색하여 1차원 map으로 변환
	// 시작점 좌표를 각각 -1씩 하고 2칸씩 한바퀴, 4칸씩 한바퀴, 6칸씩 한바퀴... 접근
	static void to1D(int[][] input) {
		int r = n / 2; // 상어좌표 r,c
		int c = n / 2;
		int idx = 1; // 상어 위치 제외 1부터 시작

		for (int level = 1; level <= n / 2; level++) {
			r -= 1;
			c -= 1;
			for (int d = 0; d < 4; d++)
				for (int i = 0; i < level * 2; i++) {
					r += dr[d];
					c += dc[d];

					map[idx++] = input[r][c];
				}
		}
	}

	// blizzard: bzdIdx를 참고하여 s만큼 0으로 만들기
	static void blizzard(int d, int s) {
		for (int i = 0; i < s; i++)
			map[bzIdx[d][i]] = 0;
	}

	// move: 구슬들 왼쪽으로 밀기
	static void move() {
		Queue<Integer> q = new ArrayDeque<Integer>();

		// map 탐색하여 0 아닌 값들 큐에 저장
		for (int i = 1; i < map.length; i++)
			if (map[i] != 0)
				q.offer(map[i]);

		// map 초기화 후 큐에서 뽑아 1번부터 채우기
		Arrays.fill(map, 0);
		for (int i = 1; i < map.length; i++) {
			if (q.isEmpty())
				break;
			map[i] = q.poll();
		}
	}

	// bomb: 연속된 구슬들 폭발
	static boolean bomb() {
		Deque<Integer> dq = new ArrayDeque<Integer>();
		int cnt = 1;
		boolean flag = false; // 한번이라도 터뜨렸는지 flag

		for (int i = 1; i < map.length; i++) {
			// 구슬 끝났으면 종료
			if (map[i] == 0)
				break;

			// 2번째 구슬부터 앞 구슬과 비교하여 카운트
			if (i != 1) {
				// 앞과 같으면 카운트
				if (map[i - 1] == map[i])
					cnt++;

				// 앞과 다르면 
				else {
					// cnt가 4이상일 때만 cnt만큼 덱에서 뽑아가며 구슬 터뜨리기
					if (cnt >= 4) {
						flag = true;

						for (int c = 0; c < cnt; c++)
							marble[dq.pollLast()]++;
					}
					cnt = 1;
				}
			}
			// 현재 구슬번호 덱에 삽입
			dq.offerLast(map[i]);
		}

		// 끝에 남은 연속된 구슬 처리
		if (cnt >= 4) {
			flag = true;
			for (int c = 0; c < cnt; c++)
				marble[dq.pollLast()]++;
		}

		// map 초기화 후 덱 앞에서부터 뽑아 1부터 저장
		Arrays.fill(map, 0);
		for (int i = 1; i < map.length; i++) {
			if (dq.isEmpty())
				break;
			map[i] = dq.pollFirst();
		}
		return flag; // 터뜨림 여부 반환
	}

	// change: 구슬 변화
	static void change() {
		// 모든 구슬 0이면 종료
		if (map[1] == 0)
			return;

		Queue<Integer> q = new ArrayDeque<Integer>();
		int cnt = 1;
		int i;

		// 2번 구슬부터 탐색
		for (i = 2; i < map.length; i++) {
			if (map[i] == 0)
				break;

			// 앞 구슬과 같으면 카운트
			if (map[i - 1] == map[i])
				cnt++;

			// 다르면 카운트와 앞 구슬 번호 큐에 삽입
			else {
				q.offer(cnt);
				q.offer(map[i - 1]);
				cnt = 1;
			}
		}

		// 마지막 구슬 처리
		q.offer(cnt);
		q.offer(map[i - 1]);

		// map 초기화 후 큐에서 뽑아 map에 1부터 저장
		Arrays.fill(map, 0);
		for (i = 1; i < map.length; i++) {
			if (q.isEmpty())
				break;
			map[i] = q.poll();
		}
	}
	/****************** Method End ******************/
}
728x90
반응형