[백준/BOJ21611] 마법사 상어와 블리자드

[백준/BOJ]

문제 #21611

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

 

 

 

 

 

내가 작성한 코드

package boj;

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

public class Main {
	static final int BLANK = 0;
	static class Pos{
		int y, x;
		
		Pos(int y, int x){
			this.y = y;
			this.x = x;
		}
		
		void change(int i) {
			y = y + dy[i];
			x = x + dx[i];
		}
	}
	
	static int[] ans = new int[4];
	
	static int[] dy = {0, -1, 1, 0, 0};
	static int[] dx = {0, 0, 0, -1, 1};
	static int[] dirNum = {3, 2, 4, 1};
	
	static int N, M;
	static int[][] map;
	static int[][] bombedMap; 
	
	static Pos shark;
	static ArrayList<int[]> DS;
	
	static int beadsCnt = 0;
	static int bombed = 0;
	public static void main(String[] args) throws Exception{
		// 입력 
		input();
		for(int m=0; m<M; ++m) {
//			던지기
			magic(DS.get(m)[0], DS.get(m)[1]);
			// 구슬 개수 업데이트
			countBeads();
			
//			땡길 것이 있는지 확인 
			while(true) {
				// 순서대로 정렬된 구슬  
				ArrayList<Integer> orderedBeads = getOrderedBeads();
				// 터지기 이전의 구슬 개수와 정렬된 구슬개수를 비교하여 재정렬여부 확인 
//				if(orderedBeads.size() == beadsCnt) break;
				// 구슬 개수 업데이트 
				
				// 재정렬 
				map = apply(orderedBeads);
				
				
				// 터져야할 구슬 정보 {없앨위치번호, 구슬번호, 구슬개수}
				ArrayList<int[]> bombedBeads = getbombedBeads();
				for(int i=0; i<bombedBeads.size(); ++i) {
					p(bombedBeads.get(i)[0] + " " + bombedBeads.get(i)[1] + " "+bombedBeads.get(i)[2]);
				}
				
				
				
				// 구슬 폭탄 
				bombed = 0;
				bomb(bombedBeads);
				countBeads();
				if(bombed == 0) break;
			}
			
			// 바꿔야할 정렬된 구슬
			ArrayList<Integer> transdBeads = getTransdBeads();
			// 재정렬 
			map = apply(transdBeads);
			
		}
		
		int ret = (1*ans[1]) + (2*ans[2]) + (3*ans[3]);
		System.out.println(ret);
	}
	
private static ArrayList<Integer> getTransdBeads() {
	Pos cur = new Pos(shark.y, shark.x);
	int repeat = 0;
	int isOdd = 1;
	
	int cnt = 0;
	int curBeadNum = 0;
	
	ArrayList<Integer> beads = new ArrayList<>();
	
	while(true) {
		for(int i=0; i<4; ++i) {
			if(isOdd % 2 == 1) {
				repeat++;
			}
			isOdd++;
			for(int j=0; j<repeat; ++j) {
				int d = dirNum[i];
				cur.change(d);
				// 0이 나왔다는건 구슬끝에 도달했다는 
				if(!inRange(cur.y, cur.x)) return beads;
//				if(map[cur.y][cur.x] == 0) return beads;
			
				if(curBeadNum == map[cur.y][cur.x]) {
					cnt++;
				}else {
					if(cur.y == shark.y && cur.x == shark.x-1) {
						cnt = 1;
						curBeadNum = map[cur.y][cur.x];
						continue;
					}
					beads.add(cnt);
					beads.add(curBeadNum);
					
					cnt = 1;
					curBeadNum = map[cur.y][cur.x];
				}
			}
		}
	}
	}

private static void bomb(ArrayList<int[]> bombedBeads) {
	for(int y=0; y<N; ++y) {
		for(int x=0; x<N; ++x) {
			for(int i=0; i<bombedBeads.size(); ++i) {
				if(bombedMap[y][x] == bombedBeads.get(i)[0]) {
					map[y][x] = BLANK;
				}
			}
		}
	}
	
	for(int i=0; i<bombedBeads.size(); ++i) {
		int beadNum = bombedBeads.get(i)[1]; // 구슬의번호 
		int beadCnt = bombedBeads.get(i)[2]; // 구슬 개수 
		ans[beadNum] += beadCnt; // beadNum번이 beadCnt개 터졌다.
		if(beadNum > 0) {
			bombed = beadCnt;
		}
	}
}

private static ArrayList<int[]> getbombedBeads() {
	Pos cur = new Pos(shark.y, shark.x);
	int repeat = 0;
	int isOdd = 1;
	
	int cnt = 0;
	int curBeadNum = 0;
	int checkNum = 1;
	bombedMap = new int[N][N];
	ArrayList<int[]> beads = new ArrayList<>();
	
	while(true) {
		for(int i=0; i<4; ++i) {
			if(isOdd % 2 == 1) {
				repeat++;
			}
			isOdd++;
			for(int j=0; j<repeat; ++j) {
				int d = dirNum[i];
				cur.change(d);
				
				if(!inRange(cur.y, cur.x)) return beads; 
				
				if(curBeadNum == map[cur.y][cur.x]) {
					cnt++;
				}else {
					if(cnt>=4) beads.add(new int[] {checkNum, curBeadNum, cnt});
					cnt = 1;
					curBeadNum = map[cur.y][cur.x];
					checkNum++;
				}
				bombedMap[cur.y][cur.x] = checkNum;
			}
		}
	}
}

private static int[][] apply(ArrayList<Integer> orderedBeads) {

	Pos cur = new Pos(shark.y, shark.x);
	int repeat = 0;
	int isOdd = 1;
	
	int[][] temp = new int[N][N];
	int idx = 0;
	
	while(true) {
		for(int i=0; i<4; ++i) {
			if(isOdd % 2 == 1) {
				repeat++;
			}
			isOdd++;
			
			for(int j=0; j<repeat; ++j) {
				int d = dirNum[i];
				cur.change(d);
				// 범위를 초과하거나 더이상 구슬을 놓을 수가 없을 때 
				if(!inRange(cur.y, cur.x) || idx >= orderedBeads.size()) return temp;
//				p(cur.y + " " + cur.x);
				temp[cur.y][cur.x] = orderedBeads.get(idx++);
			}
		}
	}
	}

private static ArrayList<Integer> getOrderedBeads() {
	
	Pos cur = new Pos(shark.y, shark.x);
	int repeat = 0;
	int isOdd = 1;
	
	ArrayList<Integer> beads = new ArrayList<>();
	
	while(true) {
		for(int i=0; i<4; ++i) {
			if(isOdd % 2 == 1) {
				repeat++;
			}
			isOdd++;
			for(int j=0; j<repeat; ++j) {
				int d = dirNum[i];
				cur.change(d);
				if(!inRange(cur.y, cur.x)) return beads;
				if(map[cur.y][cur.x] == BLANK) {
					continue;
				}
				beads.add(map[cur.y][cur.x]);
			}
		}
	}
}

	// dir방향으로 dist만큼 구슬 없애기 
	private static void magic(int dir, int dist) {
		Pos cur = new Pos(shark.y, shark.x);
		for(int d=0; d<dist; ++d) {
			cur.change(dir);
			if(!inRange(cur.y, cur.x)) return;
			map[cur.y][cur.x] = BLANK;
		}
		
	}
	
// 구슬 세기
	public static void countBeads() {
		beadsCnt = 0;
		for(int y=0; y<N; ++y) {
			for(int x=0; x<N; ++x) {
				if(map[y][x] != BLANK)  beadsCnt++;
			}
		}
	}
	
//	정상범위 
	private static boolean inRange(int y, int x) {
		return 0<= y && y<N && 0<=x && x<N;
	}
	

//	입력 
	private static void input() throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		
		map = new int[N][N];
		for(int y=0; y<N; ++y) {
			input = br.readLine().split(" ");
			for(int x=0; x<N; ++x) {
				map[y][x] = Integer.parseInt(input[x]);
			}
		}
		
		DS = new ArrayList<>();
		for(int i=0; i<M; ++i) {
			input = br.readLine().split(" ");
			DS.add(new int[]{Integer.parseInt(input[0]), Integer.parseInt(input[1])});
		}
		
		shark = new Pos(N/2, N/2);
	}

}

 

풀이 및 배운 점

2차원 배열이 아닌 1차원 배열로 풀 수 있는 방법을 다시 한 번 찾아봐야겠다.