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

문제

• BOJ 21611
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이 문제에서 놓치기 쉬운 부분은 리스트로 풀면 중간에 구슬을 이동하면서 리스트를 만들고, 구슬을 파괴하는 과정에서 구슬이 없는 경우, 즉 리스트의 사이즈가 0이 되는 경우가 발생할 수도 있다는 것이다. 따라서 중간중간에 진행하면서 list가 비었으면 종료해주어야한다.
또한, map은 구슬파괴할때나 이동할때만 필요하고 이후에 파괴,그룹만들기 부터는 굳이 map에서 달팽이이동을 해 줄 필요가 없다. 구슬을 앞으로 당기기 때문에 이는 리스트에서 작업하는게 코드 작성하기 쉽다.

1. 구슬 파괴 breaking()
   • 상어좌표로 부터 s만큼 현재 방향 d로 가면서 map[][]값을 초기화해준다.
2. 구슬 이동 moving()
   • 상어좌표로 부터 이동(달팽이)을 하면서 구슬값을 list에 넣어줌으로써 앞으로 당기는 작업을 한다.
3. 구슬 파괴 explode()
   • 구슬이 폭발할 때까지 진행하므로 폭발했는지를 저장할 flag변수를 만든다.
   • list를 돌면서 i번째 구슬과 i+1번째 구슬이 같으면 연속한 개수를 저장한다. 개수cnt가 4보다 작을 경우 새로운 리스트 tmpList에 넣고 더 크다면 넣지 않는다.
   • 폭발가능하면 그때의 구슬 번호now를 Ans[now]에 cnt수만큼 누적한다.
   • flag가 false가 될 때 까지 반복한다.
4. 구슬 그룹 넣기 makeGroup()
   • list를 돌면서 i번째 구슬과 i+1번째 구슬이 같으면 연속한 개수 cnt를 카운트하고 새로운 리스트 tmpList에 cnt와 구슬번호now를 차례대로 넣는다.
   • 그룹을 만들었으면 다시 map에 구슬리스트를 넣어주기 위해 updateMap에서 달팽이이동을 리스트 개수만큼 차례대로 넣어준다.

모든 수행이 끝나면 Ans의 0부터 3까지 값의 합을 출력해주면된다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M;
	static int mid; // 마법사 상어의 위치
	static int d, s; // 방향, 속력
	static List<Integer> list;
	static int[][] dArr = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] snailDrr = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
	static int[][] map;
	static int nowX, nowY, nowD; // 구슬 이동할 때 좌표
	static int[] Ans;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N + 1][N + 1];
		mid = (N + 1) / 2;
		Ans = new int[4];

		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 m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			d = Integer.parseInt(st.nextToken()) - 1;
			s = Integer.parseInt(st.nextToken());
			
			// 1. 구슬 파괴
			breaking(); 
			
			// 2. 구슬 이동: 일렬로 리스트 만들기
			moving();
			if(list.size() == 0) break;
			
			// 3. 구슬 폭발: 연속하는 구슬 없애기
		    while(true) {
		    	if(!explode()) break;
		    }
		    if(list.size() == 0) break;

			// 4. 그룹 만들기
			makeGroup();
		}
		
		System.out.println(Ans[1]*1+Ans[2]*2+Ans[3]*3);
	}

	private static void makeGroup() {
		List<Integer> tmpList = new ArrayList<>(); // 구슬개수, 번호 저장

		int i = 0;

		while (i < list.size()) {
			int now = list.get(i);

			if (i == list.size() - 1) { // 마지막 하나 남았으면 종료
				tmpList.add(1);
				tmpList.add(now);
				break;
			}

			int next = list.get(i + 1); // 다음 좌표

			if (now == next) { // 연속하면 총 몇개인지 세기
				int cnt = 1;
				int j = i;

				while (j < list.size() - 1) {
					if (list.get(j) == list.get(j + 1)) {
						cnt++;
						j++;
					} else break;
				}
				tmpList.add(cnt);
				tmpList.add(now);
				i = j + 1;
			} else { // 한개면
				tmpList.add(1);
				tmpList.add(now);
				i++;
			}
		}

		list = tmpList;
		updateMap(); //리스트정보->맵에 갱신
	}

	private static void updateMap() {
		int nx = mid;
		int ny = mid;
		int d = 0; // 현재 방향
		int dist = 1;
		boolean flag = true;
		int i = 0;
		map = new int[N + 1][N + 1]; // map초기화

		while (flag) {
			for (int cnt = 0; cnt < 2; cnt++) { // 2번씩 반복
				for (int go = 0; go < dist; go++) { // 방향 바뀌는 시점
					nx += snailDrr[d][0];
					ny += snailDrr[d][1];

					map[nx][ny] = list.get(i++); // 새 공을 넣어줌
					if (nx == 1 && ny == 1) return;
					if (i >= list.size()) return;
				}
				d= (d+ 1) % 4; // 방향 바꿈
			}
			dist++;
		}
	}
	
	private static boolean explode() {
		boolean flag = false; // 폭발했는지
		List<Integer> tmpList = new ArrayList<>();
		int i = 0;

		while (list.size() > 0 && i < list.size()) {
			if (i == list.size() - 1) { // 마지막 하나 남았으면 종료
				tmpList.add(list.get(i));
				break;
			}

			int now = list.get(i);
			int next = list.get(i + 1);

			if (now == next) { // 연속하면 총 몇개인지 세기
				int cnt = 1;
				int j = i;

				while (j < list.size() - 1) {
					if (list.get(j) == list.get(j + 1)) {
						cnt++;
						j++;
					} else
						break;
				}

				if (cnt < 4) for (int k = 0; k < cnt; k++) tmpList.add(now); // 4개 이상이면 안넣음
				else {
					flag = true; // 폭발했음
					Ans[now] += cnt;
				}
				i = j + 1;
			} else {
				tmpList.add(now);
				i++;
			}
		}

		list = tmpList;
		return flag;
	}

	private static void moving() {
		int nx = mid;
		int ny = mid;
		int d = 0; // 현재 방향
		int dist = 1;
		list = new ArrayList<>();

		while (true) {
			for (int cnt = 0; cnt < 2; cnt++) { // 2번씩 반복
				for (int go = 0; go < dist; go++) { // 방향 바뀌는 시점
					nx += snailDrr[d][0];
					ny += snailDrr[d][1];
					
					if (map[nx][ny] > 0) list.add(map[nx][ny]);
					if (nx == 1 && ny == 1) return;
				}
				d = (d + 1) % 4; // 방향 바꿈
			}
			dist++;
		}
	}

	private static void breaking() {
		int nx = mid;
		int ny = mid;
		
		for(int i=0; i<s; i++) {
			nx += dArr[d][0];
			ny += dArr[d][1];
			
			if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) map[nx][ny] = 0; // 구슬 파괴
		}
	}
}