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

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

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

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

public class Main_BOJ_21611 {
	static int N, M;
	static int[][] map;
	static int d, s;
	static int one=0, two=0, three=0;
	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+1][N+1];
		for (int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=1; j<=N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for (int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			d=Integer.parseInt(st.nextToken());
			s=Integer.parseInt(st.nextToken());
			dropIce(d, s);
			move(gather());
			while (explode()) {
				move(gather());
			}
			change();
		}
		System.out.println((1*one)+(2*two)+(3*three));
	}
	
	private static void dropIce(int d, int s) {
		int[] dy= {0, -1, 1, 0, 0};
		int[] dx= {0, 0, 0, -1, 1};
		int r=(N+1)/2, c=(N+1)/2;
		for (int i=0; i<s; i++) {
			r+=dy[d];
			c+=dx[d];
			map[r][c]=0;
		}
	}
	
	private static void move(ArrayList<Integer> li) {
		int[][] tempMap=new int[N+1][N+1];
		int[] dy= {0,1,0,-1};
		int[] dx= {-1,0,1,0};
		int r=(N+1)/2, c=(N+1)/2;
		int len=1;
		int d=0;
		int cnt=0;
		while (len<N) {
			int repeat = len==N-1?3:2;
			for (int j=0; j<repeat; j++) {
				for (int i=0; i<len; i++) {
					r+=dy[d];
					c+=dx[d];
					while (cnt<li.size() && li.get(cnt)==0) cnt+=1;
					if (cnt<li.size()) tempMap[r][c]=li.get(cnt++);
				}
				d=(d+1)%4;
			}
			len++;
		}
		map=tempMap;
	}
	
	public static ArrayList<Integer> gather() {
		int[] dy= {0,1,0,-1};
		int[] dx= {-1,0,1,0};
		int r=(N+1)/2, c=(N+1)/2;
		int len=1;
		int d=0;
		ArrayList<Integer> li=new ArrayList<>();
		while (len<N) {
			int repeat = len==N-1?3:2;
			for (int j=0; j<repeat; j++) {
				for (int i=0; i<len; i++) {
					r+=dy[d];
					c+=dx[d];
					li.add(map[r][c]);
				}
				d=(d+1)%4;
			}
			len++;
		}
		return li;
	}
	
	private static boolean explode() {
		int[] dy= {0,1,0,-1};
		int[] dx= {-1,0,1,0};
		int r=(N+1)/2, c=(N+1)/2;
		int len=1;
		int d=0;
		int val=-1;
		ArrayList<int[]> balls=new ArrayList<>();
		boolean isExplode=false;
		while (len<N) {
			int repeat = len==N-1?3:2;
			for (int j=0; j<repeat; j++) {
				for (int i=0; i<len; i++) {
					r+=dy[d];
					c+=dx[d];
					if (val!=map[r][c]) {
						if (balls.size()>=4) {
							isExplode=true;
							for (int[] pos : balls) {
								map[pos[0]][pos[1]]=0;
								if (val==1) one++;
								else if (val==2) two++;
								else three++;
							}
						}
						val=map[r][c];
						balls.clear();
					}
					balls.add(new int[] {r,c});
				}
				d=(d+1)%4;
			}
			len++;
		}
		return isExplode;
	}
	
	private static void change() {
		int[] dy= {0,1,0,-1};
		int[] dx= {-1,0,1,0};
		int r=(N+1)/2, c=(N+1)/2;
		int len=1;
		int d=0;
		int val=-1;
		int cnt=0;
		ArrayList<Integer> groups=new ArrayList<>();
		while (len<N) {
			int repeat = len==N-1?3:2;
			for (int j=0; j<repeat; j++) {
				for (int i=0; i<len; i++) {
					r+=dy[d];
					c+=dx[d];
					if (val!=map[r][c]) {
						if (cnt>0) {
							groups.add(cnt);
							groups.add(val);
						}
						val=map[r][c];
						cnt=0;
					}
					cnt++;
				}
				d=(d+1)%4;
			}
			len++;
		}
		move(groups);
	}



}

푼 방식이 마음에 들지 않는다.. 중복되는 코드도 너무 많고..

map과 map의 요소를 저장하는 list를 왔다갔다 할 필요 없이, 애초에 구슬을 던질 때만 list, map을 연결시켜주고 

그 밖의 과정들은 모두 list에서 처리하는게 효율성이 좋겠다.

 

아래 코드는 list를 사용해서 수정한 코드..

이 문제에서 유의할 점은 맨 마지막 번째에서 비로소 그룹이 되거나/폭발하는 case가 될 경우가 있기 때문에 이 경우를 놓쳐주지 않기 위해 map의 모든 항목에 대해서 체크가 끝나도 한번 더 count를 체크해줘야 한다는 점이다.

 

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

public class Main_BOJ_21611 {
	static int N, M;
	static int[][] map;
	static int d, s;
	static int one=0, two=0, three=0;
	static ArrayList<Integer> list;
	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+1][N+1];
		for (int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=1; j<=N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for (int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			d=Integer.parseInt(st.nextToken());
			s=Integer.parseInt(st.nextToken());
			dropIce(d, s);
			list=move(); //map=>list
			explode();
			change();
			//System.out.println(list);
			update(); //list=>map
		}
		System.out.println((1*one)+(2*two)+(3*three));
	}
	
	private static void dropIce(int d, int s) {
		int[] dy= {0, -1, 1, 0, 0};
		int[] dx= {0, 0, 0, -1, 1};
		int r=(N+1)/2, c=(N+1)/2;
		for (int i=0; i<s; i++) {
			r+=dy[d];
			c+=dx[d];
			map[r][c]=0;
		}
	}
	
	private static ArrayList<Integer> move() {
		ArrayList<Integer> li=new ArrayList<>();
		int[] dy= {0,1,0,-1};
		int[] dx= {-1,0,1,0};
		int r=(N+1)/2, c=(N+1)/2;
		int len=1;
		int d=0;
		while (len<N) {
			int repeat = len==N-1?3:2;
			for (int j=0; j<repeat; j++) {
				for (int i=0; i<len; i++) {
					r+=dy[d];
					c+=dx[d];
					if (map[r][c]!=0) li.add(map[r][c]);
				}
				d=(d+1)%4;
			}
			len++;
		}
		return li;
	}
	
	
	private static void explode() {
		while (true) {
			ArrayList<Integer> temp=new ArrayList<>();
			boolean isExplode=false;
			int value=-1;
			int cnt=0;
			for (int i=0; i<list.size(); i++) {
				int num=list.get(i);
				temp.add(num);
				if (value!=num) {
					if (cnt>=4) {
						isExplode=true;
						for (int j=0; j<cnt+1; j++) {
							temp.remove(temp.size()-1);
						}
						temp.add(num);
						if (value==1) one+=cnt;
						else if (value==2) two+=cnt;
						else three+=cnt;
					}
					value=num;
					cnt=1;
				}
				else cnt++;
			}
			if (cnt>=4) {
				for (int j=0; j<cnt; j++) {
					temp.remove(temp.size()-1);
				}
				if (value==1) one+=cnt;
				else if (value==2) two+=cnt;
				else three+=cnt;
			}
			if (!isExplode) break;
			list=temp;
		}
	}
	
	private static void change() {
		ArrayList<Integer> temp=new ArrayList<>();
		int val=-1;
		int cnt=0;
		for (int i=0; i<list.size(); i++) {
			int num=list.get(i);
			if (val!=num) {
				if (cnt>0) {
					temp.add(cnt);
					temp.add(val);
				}
				val=num;
				cnt=1;
			}
			else {
				cnt++;
			}
		}
		if (cnt>0) {
			temp.add(cnt);
			temp.add(val);
		}
		list=temp;
	}
	
	private static void update() {
		int[] dy= {0,1,0,-1};
		int[] dx= {-1,0,1,0};
		int r=(N+1)/2, c=(N+1)/2;
		int len=1;
		int d=0;
		int cnt=0;
		while (len<N) {
			int repeat = len==N-1?3:2;
			for (int j=0; j<repeat; j++) {
				for (int i=0; i<len; i++) {
					r+=dy[d];
					c+=dx[d];
					if (cnt<list.size()) map[r][c]=list.get(cnt++);
					else map[r][c]=0;
				}
				d=(d+1)%4;
			}
			len++;
		}
	}



}