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

문제 링크

핵심

달팽이 모양으로 배열을 조회하는 것을 구현하는 것이 핵심이였다.

단순 구현 문제였다. 문제에서 주어진 대로 구현해야 할 것들은 다음과 같았다.

1. 블리자드 마법 후, 달팽이 모양 순서대로 탐색 할 때 중간에 빈 칸이 있을 경우 앞으로 당기기
2. 4개 이상 연속된 구슬을 파괴시킨 후 달팽이 모양 순서대로 탐색 할 때 중간에 빈 칸이 있을 경우 앞으로 당기고, 더 이상 4개 이상 연속된 구슬이 없을 때 까지 반복하기
3. 구슬 그룹을 그룹의 구슬 갯수, 구슬 번호로 변환시키기

1번을 구현할 때 현재 칸이 0일 때, 다음 칸의 구슬 번호를 당겨오는 방식으로 진행했는데, 이렇게 될 경우 두 번째 0을 만날 때 부터 현재 칸이 0, 다음 칸도 0인 상황이 생겨 문제가 발생했다. 이 때문에 큐를 생성해놓고, 남은 구슬을 순서대로 큐에 넣어 놓은 뒤 그때 그때 board 배열에 달팽이 모양으로 큐의 원소를 넣는 방법으로 해결했다.

2번의 경우 destroy() 메서드에서 while(!q.isEmpty()) { ~ } 반복문을 진행할 때, 맨 끝의 원소가 가령 2 2 2 2 2 2 2 이렇게 들어있었다면, 반복문을 빠져 나올 때 answer에 누적이 안 된 상태로 나오기 때문에 반복문 종료 후 이를 처리해 주는 부분이 필요했다. (이 부분이 없으면 제출 시 77%에서 오류가 발생함)

3번의 경우 temp 큐의 원소를 q 큐로 옮기는 과정에서, 문제의 "만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다." 부분 때문에 N*N-1개 이상의 원소는 필요 없으므로 반복문을 멈춰주는 부분이 필요했다. (이 부분이 없으면 시간 초과가 발생함)

코드

package bj21611;

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

public class Main_bj_21611_마법사상어와블리자드 {
	
	static int N,M,sr,sc,answer;
	static int[][] board;
	static int[] dr = {0,-1,1,0,0}, dc = {0,0,0,-1,1};	// 1: 상, 2: 하, 3: 좌, 4: 우
	static int[] mr = {0,1,0,-1}, mc = {-1,0,1,0}; // 0: 좌, 1: 하, 2: 우, 3: 상
	static Queue<Integer> q = new ArrayDeque<>();
	
	// 블리자드
	static void blizard(int d, int s) {
		for(int i=1; i<=s; i++) {
			board[sr+(dr[d])*i][sc+(dc[d])*i] = 0;
		}
		make_queue();
	}
	
	// board 배열 초기화
	static void reset() {
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				board[i][j] = 0;
			}
		}
	}
	
	// 달팽이 모양 순서대로 큐에 구슬 삽입
	static void make_queue() {
		int r=sr, c=sc, d=0, time=1;
		
		while(r!=1 || c!=1) {
			for(int i=0; i<time; i++) {
				if(r==1 && c==1) return;
				r+=mr[d];
				c+=mc[d];
				if(board[r][c]!=0) q.offer(board[r][c]);
			}
			d = (d+1)%4;
			
			for(int i=0; i<time; i++) {
				if(r==1 && c==1) return;
				r+=mr[d];
				c+=mc[d];
				if(board[r][c]!=0) q.offer(board[r][c]);
			}
			d = (d+1)%4;
			time++;
		}
	}
	
	// 큐에 들어있는 구슬을 달팽이 순서대로 board 배열에 재배치
	static void move() {
		reset();
		int r=sr, c=sc, d=0, time = 1;
		
		while(!q.isEmpty()) {
			for(int i=0; i<time; i++) {
				if(q.isEmpty() || (r==1 && c==1)) return;
				r+=mr[d];
				c+=mc[d];
				board[r][c] = q.poll();
			}
			d = (d+1)%4;
			
			for(int i=0; i<time; i++) {
				if(q.isEmpty() || (r==1 && c==1)) return;
				r+=mr[d];
				c+=mc[d];
				board[r][c] = q.poll();
			}
			d = (d+1)%4;
			time++;
		}	
	}
	
	// 4개 이상 연속된 구슬을 파괴한 후 답에 누적
	static void destroy() {
		make_queue();		
		boolean flag = true;
		Queue<Integer> temp = new ArrayDeque<>();		
		while(flag) {
			if(q.isEmpty()) return;
			int num = q.poll(), cnt = 1, cur = 0;
			temp = new ArrayDeque<>();		
			flag = false;
			while(!q.isEmpty()) {
				cur = q.poll();
				if(cur==num) {
					cnt++;
				}
				else {
					if(cnt<4) {
						for(int i=0; i<cnt; i++) {
							temp.offer(num);
						}
					}
					else {
						flag = true;
						answer += cnt*num;
					}
					num = cur;
					cnt = 1;
				}
			}
			if(cnt>=4) {
				answer += cnt*num;
			}
			else {
				for(int i=0; i<cnt; i++) temp.offer(cur);
			}
			
			q = new ArrayDeque<>();
			
			while(!temp.isEmpty()) {
				q.offer(temp.poll());
			}
		}
	}
	
	// 연속된 구슬의 갯수와 구슬 번호로 구슬 변환
	static void change() {
		make_queue();
		Queue<Integer> temp = new ArrayDeque<>();
		if(q.isEmpty()) return;
		int cnt = 1, num = q.poll();
		while(!q.isEmpty()) {
			int cur = q.poll();
			if(cur == num) cnt ++;
			else {
				temp.offer(cnt);
				temp.offer(num);
				cnt = 1;
				num = cur;
			}
		}
		temp.offer(cnt);
		temp.offer(num);
		q = new ArrayDeque<>();
		
		while(!temp.isEmpty()) {
			q.offer(temp.poll());
			if(q.size()==N*N-1) break;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[N+1][N+1];
		sr = sc = (N+1)/2;
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=1; j<=N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(in.readLine());
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			
			blizard(d,s);
			move();
			destroy();
			move();
			change();
			move();
			
		}
		
		System.out.println(answer);
		
	}
}