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

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

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

 

온풍기 풀고 이거 푸니까 살거같다.. ㅋㅋ ㅠ

 

 

우선 달팽이 규칙

솔직히 이건 까먹어도 바로 그 자리에서 찾아낼 수 있는 쉬운 규칙이다.

 

방법

• d, s로 파괴할거 파괴 (이거는 ans에 담지 않는다)
• 달팽이 규칙으로 map의 숫자들 전부 Queue에 넣기
• Queue 1개씩 뽑아서 연속된 숫자 개수 >= 4 인 경우 폭파시킴
• 폭파시킨 개수는 HashMap<숫자, 개수> 에 넣고 최종 ans에 숫자 * 개수 더함
• 위에 두개 반복하면서 HashMap의 key값이 0이 나오면 반복문 break
• 제시된 규칙으로 개수 - 숫자 - 개수 - 숫자 .. 이런식으로 Queue 값 바꿔줌
• 달팽이 규칙으로 Queue값 map에 넣기

 

주의할 점

• Queue에서 ball 꺼낼때 Q가 비어있는 경우 생각하기 ! (저는 초기값 들어가서 -1이 찍혔습니다)
• 연속 개수 4이상인 경우 폭파시킬때, 마지막에 폭파처리 되었는지 확인 & HashMap 반영됐는지 확인
• 다음 반복때 Queue에 담기 전에 clear() 해주기 (이전에 담지 못한 나머지가 있을 수 있음)

 

도움되었던 반례 - 마지막에 Map 찍어보세요

3 1 1 1 1 1 0 1 1 1 1 3 1 답 : 7

3 1 0 2 2 2 0 1 2 2 2 4 1 답 : 12

출처 : https://wizii.tistory.com/32 / https://www.acmicpc.net/board/view/71185

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj21611 {
	public static long ans=0;
	public static int N, M, sharkX, sharkY;
	public static int[][] map;
	
	public static HashMap<Integer, Integer> exp = new HashMap<>();
	
	public static int[] dx = {0, -1, 1, 0, 0};
	public static int[] dy = {0, 0, 0, -1, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		sharkX = (N+1)/2-1;
		sharkY = (N+1)/2-1;
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		for(int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			
			destory(d,s);
			collectBall();
			
			while(remove()!=0) {
				setAns();
			}
			
			setBall();
			newMap();
			
		}
		System.out.println(ans);
	}
	
	public static void setAns() {
		for(int n : exp.keySet()) {
			ans += n * exp.get(n);
		}
			
	}
	
	public static void setBall() {
		int last = -1;
		int cnt = 0;
		if(q.size()==0)
			return ;
		
		Queue<Integer> newQ = new LinkedList<>();
		while(!q.isEmpty()) {
			if(q.peek()==last) {
				q.poll();
				cnt++;
			}else {
				if(last != -1) {
					newQ.add(cnt);
					newQ.add(last);
				}
				
				last = q.poll();
				cnt = 1;
			}
		}
		
		newQ.add(cnt);
		newQ.add(last);
		
		q.addAll(newQ);
	}
	
	public static int remove() {
		int last = -1;
		int cnt = 0;
		Queue<Integer> newQ = new LinkedList<>();
		exp = new HashMap<>();
		
		while(!q.isEmpty()) {
			if(q.peek()==last) {
				q.poll();
				cnt++;
			}else {
				if(cnt < 4) {
					for(int i=0; i<cnt; i++)
						newQ.add(last);
				}else {
					exp.put(last, exp.getOrDefault(last, 0)+cnt);
				}
				
				last = q.poll();
				cnt = 1;
			}
			//System.out.println(last);
		}
		
		if(cnt < 4) {
			for(int i=0; i<cnt; i++)
				newQ.add(last);
		}else {
			exp.put(last, exp.getOrDefault(last, 0)+cnt);
		}
		
		q.addAll(newQ);
		return exp.keySet().size();
	}
	
	public static void printMap() {
		System.out.println("====PRINT MAP====");
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void newMap() {
		int x = sharkX, y = sharkY;
		map = new int[N][N];
		
		boolean notArea = false;
		int level = 1;
		while(isInArea(x,y) && !q.isEmpty()) {
			// 왼쪽 이동
			for(int i=0; i<level; i++) {
				y--;
				if(!isInArea(x,y) || q.isEmpty()) {
					notArea = true;
					break;
				}
				map[x][y] = q.poll();
			}
			if(notArea) break;
			
			// 아래 이동
			for(int i=0; i<level; i++) {
				x++;
				if(!isInArea(x,y) || q.isEmpty()) {
					notArea = true;
					break;
				}
				map[x][y] = q.poll();
			}
			if(notArea) break;
			
			level++;
			
			// 오른쪽 이동
			for(int i=0; i<level; i++) {
				y++;
				if(!isInArea(x,y) || q.isEmpty()) {
					notArea = true;
					break;
				}
				map[x][y] = q.poll();
			}
			if(notArea) break;
			
			
			// 위로 이동
			for(int i=0; i<level; i++) {
				x--;
				if(!isInArea(x,y) || q.isEmpty()) break;
				map[x][y] = q.poll();
			}
			level++;
		}
		q.clear();
	}
	
	public static Queue<Integer> q = new LinkedList<>();
	public static void collectBall() {
		int x = sharkX, y = sharkY;
		q.clear();
		
		boolean notArea = false;
		int level = 1;
		while(isInArea(x,y)) {
			
			// 왼쪽 이동
			for(int i=0; i<level; i++) {
				y--;
				if(!isInArea(x,y)) {
					notArea = true;
					break;
				}
				if(map[x][y]!=0)
					q.add(map[x][y]);
			}
			if(notArea) break;
			
			// 아래 이동
			for(int i=0; i<level; i++) {
				x++;
				if(!isInArea(x,y)) {
					notArea = true;
					break;
				}
				if(map[x][y]!=0)
					q.add(map[x][y]);
			}
			if(notArea) break;
			
			level++;
			
			// 오른쪽 이동
			for(int i=0; i<level; i++) {
				y++;
				if(!isInArea(x,y)) {
					notArea = true;
					break;
				}
				if(map[x][y]!=0)
					q.add(map[x][y]);
			}
			if(notArea) break;
			
			// 위로 이동
			for(int i=0; i<level; i++) {
				x--;
				if(!isInArea(x,y)) break;
				if(map[x][y]!=0)
					q.add(map[x][y]);
			}
			
			level++;
		}
	}
	
	
	public static void destory(int d, int s) {
		int sx = sharkX+dx[d], sy = sharkY+dy[d];
	
		while(isInArea(sx, sy) && (s--)>0) {
			map[sx][sy]=0;
			sx+=dx[d];sy+=dy[d];
		}
	}
	
	public static boolean isInArea(int x, int y) {
		return x>=0 && x<N && y>=0 && y<N;
	}
}