BOJ 백준 21611 마법사 상어와 블리자드

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

 

[ 문제 요약 ]

• 맵은 N*N 크기가 주어지며 N은 항상 홀수입니다. 가장 왼쪽 위 칸은 1,1이고, 가장 오른쪽 아래 칸은 N, N입니다.
• 상어는 맵의 정중앙에 있습니다. [ (N+1)/2 , (N+1)/2) ]
• 구슬의 이동은 중앙에서 왼쪽 방향부터 달팽이 모양으로 이동합니다.
• 상어가 있는 칸 외에 모든 칸에는 구슬이 들어갈 수 있습니다.
• 구슬은 1,2,3번 구슬이 있습니다.
• 같은 번호를 가진 구슬이 번호가 연속하는 칸에 있으면, 그 구슬을 연속하는 구슬이라 합니다.

1. 구슬 파괴 단계 마법을 사용해 구슬을 파괴합니다. 마법을 사용하려면 방향 di와 거리 si를 정해야 합니다. 총 4가지 방향 ↑, ↓, ←, →이 있고, 정수 1,2,3,4로 나타냅니다. 상어는 di 방향으로 거리가 si 이하인 모든 칸에 얼음을 던져 그 칸에 있는 구슬을 모두 파괴합니다. 구슬이 파괴되면 그 칸은 구슬이 들어있지 않은 빈칸이 됩니다.
2. 구슬 이동 및 폭발 반복 단계 그 후 빈칸의 번호보다 큰 번호의 구슬들이 작은 번호의 칸으로 연쇄적으로 모두 이동합니다. 그리고 그다음에 같은 구슬 번호가 4개 이상 연속할 때 구슬이 폭발합니다. 폭발 후 빈칸이 생기면 다시 구슬이 이동합니다. 이 과정을 폭발하는 구슬이 없을 때까지 반복합니다.
3. 구슬 변화 단계 연속하는 구슬은 하나의 그룹이라 합니다. 하나의 그룹은 두 개의 구슬 A와 B로 변합니다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이고, B는 그룹을 이루고 있는 구슬의 번호입니다. 구슬은 다시 그룹의 순서대로 1번 칸부터 차례대로 A, B의 순서로 칸에 들어갑니다. 만약 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그런 구슬들은 사라집니다.

• 위 와 같은 단계를 M 번 반복할 때, 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력합니다. 최초 주어지는 구슬들은 4개 이상 연속하는 구슬은 없습니다.

 

[ 테스트 케이스 설명 ]

7 1 // 맵크기(3<=49), 스킬반복횟수(1<=100)
0 0 0 0 0 0 0 // 구슬의 정보가 주어지며 없으면 0이주어짐 상어칸은 항상 0임
3 2 1 3 2 3 0
2 1 2 1 2 1 0
2 1 1 0 2 1 1
3 3 2 3 2 1 2
3 3 3 1 3 3 2
2 3 2 2 3 2 3
2 2 // 스킬의 방향(1<=4)과 거리(1<=(N-1)/2)
답 : 28

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

[ 정답 해설 ]

구슬 파괴 → 맵을 시작점에서 달팽이 모양으로 돌며 순서대로 큐에 담음 → 큐에서 4개 이상 연속되는 구슬들이 없을 때까지 폭파 → 큐에 담긴 정보를 그룹화 후 변경 → 큐 정보를 달팽이 모양으로 돌며 map에 저장 → 구슬 파괴 및 로직 반복

위와 같은 형태로 구현만 하면 됩니다.

[ 정답 코드 ]

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

class Main{
	
	static final int dxy[][] = {{0,-1},{1,0},{0,1},{-1,0}};// 달팽이 방향 순회시 사용
	static final int dxy2[][] = {{-1,0},{1,0},{0,-1},{0,1}};// 구슬 파괴시 사용
	static ArrayDeque<Integer> q;
	static boolean[][] visit;
	static boolean flag;
	static int[][] map;
	static int sy, sx;
	static int N, M;
	static int res;
	
	
	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());// 맵 크기(3<=49)
		M = Integer.parseInt(st.nextToken());// 스킬 반복 횟수(1<=100)
		flag = false;
		sy = sx = (N + 1) / 2;
		q = new ArrayDeque<>();
		map = new int[N + 2][N + 2];
		visit = new boolean[N + 2][N + 2];
		
		for(int i=0; i<N + 2; i++)
			map[i][N + 1] = map[N + 1][i] = map[0][i] = map[i][0] = -1;
		
		for(int y=1; y<=N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=1; x<=N; x++)
				map[y][x] = Integer.parseInt(st.nextToken());
		}
		
		while(M-->0)
		{
			st = new StringTokenizer(br.readLine());
			int dir = Integer.parseInt(st.nextToken()) - 1;
			int dist = Integer.parseInt(st.nextToken());
			
			delete(dir, dist); // 마법 시전

			moveAndExplosion();// 구슬 이동 및 폭발 반복

			groupChange();// 그룹 변경
		}
		
		System.out.print(res);
	}
	static void delete(int dir, int dist) {
		int ny = sy;
		int nx = sx;
		while(dist-->0)
		{
			ny += dxy2[dir][0];
			nx += dxy2[dir][1];
			
			if(map[ny][nx] < 0)
				return;
			
			map[ny][nx] = 0;
		}
	}
	static boolean moveAndExplosion() {
		q.clear();
		
		search(sy, sx, 3, 1);// 맵을 돌면서 0이 아닌 구슬의 숫자를 q에 넣음
		
		return explosion();// q에서 4개이상 연속된 구슬이 없을 때 까지 폭파 시키며 최종 결과가 q에 담겨 있음
	}
	static void groupChange() {
		// q에 담긴 값을 변환하여 q2에 담음
		ArrayDeque<Integer> dummy = new ArrayDeque<>();
		ArrayDeque<Integer> q2 = new ArrayDeque<>();
		
		int prev = -1;
		
		while(!q.isEmpty())
		{
			int n = q.poll();
			
			if(prev != n && dummy.size() > 0)
			{
				q2.add(dummy.size());
				q2.add(dummy.poll());
				dummy.clear();
			}
			
			dummy.add(n);
			prev = n;
		}
		
		if(dummy.size() > 0)
		{
			q2.add(dummy.size());
			q2.add(dummy.poll());
		}
		
		q = q2;
		
		search(sy, sx, 3, 2);// 맵을 돌면서 q값을 순차적으로 map에 다시 넣음
	}
	static boolean explosion() {
		boolean isContinue = false;
		int prevSize = -1;
		
		while(prevSize != q.size())
		{
			ArrayDeque<Integer> dummy = new ArrayDeque<>();
			ArrayDeque<Integer> q2 = new ArrayDeque<>();
			
			prevSize = q.size();
			
			int prevNum = prevSize != 0 ? q.peek() : 0;
			
			while(!q.isEmpty())
			{
				int n = q.poll();// 값을 꺼내옴
				
				if(n == prevNum)
				{
					dummy.add(n);// 이전과 같다면 dummy에 넣고 스킵
					continue;
				}
				
				
				if(dummy.size() >= 4)// 더미에 들어간 사이즈가 4개 이상이면 폭발시키고 결과에 플러스
				{
					res += dummy.size() * dummy.poll();
					isContinue = true;
				}
				else
					q2.addAll(dummy);// 사이즈가 3이하면 q2에 그대로 담음
				
				dummy.clear();
				dummy.add(n);
				prevNum = n;
			}
			if(dummy.size() >= 4)// 더미에 들어간 사이즈가 4개 이상이면 폭발시키고 결과에 플러스
			{
				res += dummy.size() * dummy.poll();
				isContinue = true;
			}
			else// 사이즈가 3이하면 q2에 그대로 담음
			{
				q2.addAll(dummy);
				dummy.clear();
			}
			
			q = q2;
		}
		return isContinue;
		
	}
	static void search(int y, int x, int dir, int excute) {
		flag = !flag;
		visit[y][x] = flag;
		
		while(map[y][x] >= 0)
		{
			// 시작하자마자 방향을 꺾을 수 있으면 꺾고 못먺으면 그대로 감
			int nextDir = (dir + 1) % 4;
			
			int ny = y + dxy[nextDir][0];
			int nx = x + dxy[nextDir][1];
			
			if(visit[ny][nx] != flag)// 갈 수 있다면
			{
				dir = nextDir;// 그 방향으로 감
			}
			// 해당 방향으로 감
			ny = y + dxy[dir][0];
			nx = x + dxy[dir][1];
			
			// 맵을 벗어나면 break
			if(map[ny][nx] < 0)
				break;
			
			visit[ny][nx] = flag;// 방문 처리
			
			y = ny;
			x = nx;
			
			if(excute == 1) // 맵 정보를 큐에넣는 연산이면
			{
				if(map[ny][nx] > 0) // 값이 유효할 때 큐에 데이터 삽입
					q.add(map[ny][nx]);
			}
			else if(excute == 2) // 큐 값을 map에 매핑하는 연산이면 큐 데이터가 있을 때 넣고 없으면 0 대입
			{
				map[ny][nx] = q.isEmpty() ? 0 : q.poll();
			}
		}
	}
}