BOJ - 마법사 상어와 블리자드 21611번 (JAVA)

❓ 문제 - 백준 마법사 상어와 블리자드 21611번 - JAVA 풀이법

 

출처 

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

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

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 각 1, 2, 3, .... N*N-1번의 위치 정보를 Node객체의 배열에다가 저장하여 접근 처리한다.
• 1번 부터 n*n-1까지의 위치 정보를 구하면 상어가 있는 위치 (n/2, n/2)부터 좌->하->우->상을 반복하면서 토네이도 형태로 되어 있다. 이 위치에서 한 방향을 반복하는 횟수는 1, 1, 2, 2, 3, 3, ..., n-1, n-1, n이다. 그래서 한 방향을 num 만큼 반복했으면 방향을 전환시켜준다. 그리고 반복 횟수(num)이 몇 번 사용 됐는지를 same_cnt로 관리하며 해당 방향을 num만큼 이동시키면 1 증가시킨다. 만약 same_cnt가 2라면 반복 횟수(num)을 1 증가시킨다.
• m번의 마법을 시전하면서 얼음파편 던지기 -> 당기기(pull()) -> 연속하는 4개이상의 구슬 폭발과 당기기 처리를 하며 폭발이 없을 때까지 반복처리한다. -> 구슬 갯수의 변화(change())를 맞춰서 구현한다.

 

2. 얼음 파편 던지기

• 상어의 위치(n/2, n/2)에서 해당 방향과 속력안에 포함되는 범위 안에 다 얼음 파편을 던져 0으로 처리한다.

3. pull()

• 위치의 번호 1 ~ n*n-1를 순서대로 접근하면서 만약 현재 위치가 비어있다면 다음 숫자에 위치한 구슬을 당겨와야 하므로 다음에 위치한 구슬의 번호를 찾아와 현재 위치에 해당 구슬을 정보를 넣어줌 처리한다.

4. bomb()

• bomb_chk라는 변수를 통해 연속하는 4개이상의 구슬이 폭발했는지 안했는지를 체크한다.
• 연속하는 4개 이상의 구슬이 같은지 확인하기 위해 투포인터를 활용한다. 현재 시작 위치로 부터 end를 1씩 증가하면서 연속하는 구슬이 몇 개인지를 카운트 증가해주고, 만약 현재 구슬과 다른 정보가 나오면 break 해준다.
• 만약 연속하는 구슬의 갯수가 4개 이상이라면 폭발 처리 true로 해주고, 시작 위치 ~ end 직전위치까지 다 0으로 구슬을 폭발시켜준다. 그리고 start를 end의 위치로 옮기고 end를 start+1로 옮겨서 위의 과정을 반복하면서 다른 연속하는 구슬이 존재하는지 반복해서 찾는다.

5. change()

• 구슬의 색깔의 갯수, 색깔의번호로 구슬을 그룹짓기 위해 투포인터를 활용한다.
• 현재 시작 위치로 부터 end를 증가시키면서 현재 구슬이 몇개 연속적으로 이어져 있는지 파악하며, 해당 갯수만큼을 차곡 차곡 map_copy에 갯수, 구슬의 종류 순으로 넣어주며, 만약 이렇게 넣어준 데이터가 n*n 이상이 되면 더이상 그룹을 넣을 수 없기 때문에 종료해준다.

6. 느낀점

• 처음에 map에 위치를 접근할 때 hashmap을 활용했는데 시간초과가 났다..
• 이게 n이 최대 49이므로 대략 2500개의 위치 정보값을 생성하기 때문에.. 해쉬를 넣고 빼고 변경하는데 큰 시간이 들어가는 것 같다. 최대한 고정된 데이터 범위에서 데이터를 접근하려면 배열을 활용해서 구현해야겠다..!

 

 

 

💻 소스코드

// BOJ - 마법사 상어와 블리자드(21611번)
// 구현

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

public class Main_21611 {
	public static int n, m;
	public static int[] score;
	public static int[][] map;
	public static Node[] node_map;
	
	public static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static int[] dx = {0, 1, 0, -1};
	public static int[] dy = {-1, 0, 1, 0};
	public static int[] m_dir = {0, 3, 1, 0, 2};
	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];
		node_map = new Node[n*n];
		hash = new HashMap<>();
		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());
			}
		}
	
		int x = n/2;
		int y = n/2;
		int cnt = 1;
		int dir = 0;
		int num = 1;
		int nx = x;
		int ny = y;
		outer : while(true) {
			int same_dir = 0;
			int same_cnt = 0;
			while(true) {
				if(nx == 0 && ny == 0) break outer;
				nx += dx[dir];
				ny += dy[dir];
				node_map[cnt++] = new Node(nx, ny);
				same_dir++;
				if(same_dir == num) {
					same_cnt++;
					dir = (dir+1)% 4;
					same_dir = 0;
					if(same_cnt == 2) {
						same_dir = 0;
						same_cnt = 0;
						num++;
						break;
					}
				} 
			}
		}
		score = new int[4];
		
		for(int k=0;k<m;k++) {
		
			st = new StringTokenizer(br.readLine(), " ");
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			
			// 얼음파편 던지기
			int s_x = n/2;
			int s_y = n/2;
			for(int i=1;i<=s;i++) {
				int n_sx = s_x + dx[m_dir[d]] * i;
				int n_sy = s_y + dy[m_dir[d]] * i;
				map[n_sx][n_sy] = 0;
			}
			
			// 당기기
			pull();
		
			// 연속하는 4개이상 폭발 -> 폭발없을 때까지 반복
			while(bomb()) {
				pull();
			
			}
			
			// 구슬 갯수 변화
			change();
		
		}
		
		int sum = 0;
		for(int i=1;i<=3;i++) {
			sum += (score[i]*i);
		}
		System.out.println(sum);
		
	}
	
	public static void print() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void change() {

		int start = 1;
		int end = start +1;
		int[][] map_copy = new int[n][n];
		int map_cnt = 1;
		while(true) {
			if(start == n*n-1) break;
			Node node = node_map[start]; 
			int num = map[node.x][node.y];
			if(num == 0) break;
			int cnt = 1;
			while(true) {
				Node next = node_map[end];
				if(end >= n*n) break;
				if(map[next.x][next.y] == num) {
					end++;
					cnt++;
					continue;
				} else {
					break;
				}
			}
			Node nd = node_map[map_cnt++];
			map_copy[nd.x][nd.y] = cnt;
			nd = node_map[map_cnt++];
			map_copy[nd.x][nd.y] = num;
			start = end;
			end = start+1;
			if(map_cnt >= n*n) {
				break;
			}
		}
	
		map = map_copy;
	
	}
	
	
	public static boolean bomb() {
		boolean bomb_chk = false;
		int start = 1;
		int end = start +1;
		
		while(true) {
			if(start == n*n-1) break;
			Node node = node_map[start];
			int num = map[node.x][node.y];
			if(num == 0) break;
			int cnt = 1;
			while(true) {
				Node next = node_map[end];
				if(end >= n*n) break;
				if(map[next.x][next.y] == num) {
					end++;
					cnt++;
					continue;
				} else {
					break;
				}
			}
			
			if(cnt >= 4) {
				bomb_chk = true;
			
				score[num] += cnt;
				for(int i=start;i<end;i++) {
					Node bomb_node = node_map[i];
					map[bomb_node.x][bomb_node.y] = 0;
				}
			}
			start = end;
			end = start+1;
		}
		
		
		
		return bomb_chk;
	}
	
	public static void pull() {
		for(int i=1;i<n*n;i++) {
			Node node = node_map[i];
			if(map[node.x][node.y] != 0) continue;
			for(int j=i+1;j<n*n;j++) {
				Node nt_node = node_map[j];
				if(map[nt_node.x][nt_node.y] != 0) {
					map[node.x][node.y] = map[nt_node.x][nt_node.y];
					map[nt_node.x][nt_node.y] = 0;
					break;
				} 
			}
		}
	}

}