🔰 문제
💡 접근방식
마법사 상어와 토네이도 문제를 풀어봤다면 조금 익숙하게 느껴졌을 수도 있다.
토네이도 문제에서도 위와 같이 중심에서부터 바깥으로 퍼져나가는 형태였는데
블리자드 문제 또한 중심에서 밖으로 퍼져나가는 형태였다.
문제에서 주어진대로 구현하면 되는데 여기서 중요한게 처음에 시작할 때 각 칸의 번호를 미리 세팅해두고 시작하는게 편하다. 나중에 구현할 때 다음 칸으로 가려 하면 머리 터진다..
- 토네이도 칸 번호 세팅
- d 방향 s 거리만큼 구슬 파괴
- 구슬 안 쪽으로 당기기
- 4개 이상 연속하는 구슬 폭발
- 구슬 안 쪽으로 당기기
- 4~5 과정을 더 이상 폭발할 구슬이 없을 때까지 반복
- 하나의 그룹을 구슬 A(구슬 개수), 구슬 B(구슬 번호)로 나누기
문제에서 하라는 대로 열심히 구현하면 된다..
구슬 안 쪽으로 당기는 부분을 구현하는 게 2번이나 사용되기 때문에 중요했다.
💦 풀면서 실수, 놓친 점
구슬 당기기
처음에 구슬 당길 때 빈칸 생기면 바로 다음 칸의 값을 끌어오는 방식으로 하였다. 하지만 다음 칸도 0일 수 있었기에 자기 칸 번호보다 큰 애들을 오름차순으로 탐색하면서 0이 아닌 최소 칸 번호를 찾아야 했다. 여기를 구현할 때 어떻게 할 지 막막헀는데 처음에 x, y 좌표에 매칭되는 칸 번호를 미리 세팅해놓으면 쉽게 해결할 수 있었다.
구슬을 안쪽으로 당길 때 자기 자신의 칸 번호보다 작은 곳은 무조건 꽉 차 있다고 가정하고, 빈 칸을 발견하면 자기 칸 번호보다 큰 것 중에 0이 아닌 것의 칸 번호를 얻어와서 그 칸의 요소를 현재 칸으로 당겨왔다. 이런 식으로 모든 칸(N*N)을 돌 때까지 실행하였다.
private static void moveInside() { // 2. 구슬 파괴 후 빈칸 생긴 칸 기준으로 당기기
for (int i = 1; i < N * N; i++) {
int cx = xy[i][0];
int cy = xy[i][1];
if (map[cx][cy] == 0) {
int[] nxy = find(i); // i보다 큰 것중에 0 아닌 값 찾기
int nx = nxy[0];
int ny = nxy[1];
map[cx][cy] = map[nx][ny];
map[nx][ny] = 0;
}
}
}연속하는 4개 터뜨리기
의외로 연속하는 4개 터뜨리기 부분을 구현하는데 애먹었다.
나같은 경우는 연속하는 개수와, 연속하는 부분의 x, y 좌표를 모두 저장하여 구현하였다. 그런데 이 때 연속하는 개수가 0개인 완전 새로운 상태에서 map[x][y]==map[nx][ny]인 경우와 이미 연속하고 있는 상태에서 map[x][y]==map[nx][ny]인 경우, 개수 증가량과 x, y좌표 저장하는 방식이 달라서 더욱 간단하게 구현할 수 있을지 고민하다가 떠올리지 못 해서 그냥 분기문으로 나눴다.
if (cnt == 0 && map[x][y] != 0 && map[x][y] == map[nx][ny]) { // cnt=0일 때 map[x][y]==map[nx][ny]이면 cnt + 2 처리
cnt += 2;
list.add(new int[] { x, y });
list.add(new int[] { nx, ny });
} else if (cnt != 0 && map[x][y] != 0 && map[x][y] == map[nx][ny]) { // cnt >0인 경우, 계속 연속되고 있는 상황이기 때문에 map[nx][ny] 개수만 추가
cnt++;
list.add(new int[] { nx, ny });
}또한 여기 부분은 칸 번호 세팅을 하지 않은 상태에서 구현한 메소드로 코드가 많이... 더럽다. 저기는 다음에 풀 때 꼭 고쳐야 할 것 같다. 😂😂
🕑 소요시간
1시간 45분
💻 풀이
import java.io.*;
import java.util.*;
// BOJ / G1 / 마법사 상어와 블리자드 / 1시간 45분
public class Main_21611 {
static int N, M;
static int map[][];
static int d[], s[]; // 방향, 속력
static int dx[] = { 0, -1, 1, 0, 0 }; // 1~4 상하좌우
static int dy[] = { 0, 0, 0, -1, 1 };
static int res; // 구슬 폭발 합
static int xy[][]; // 좌표
public static void main(String[] args) throws Exception {
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];
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());
}
d = new int[M]; // M개의 방향 d
s = new int[M]; // M개의 거리 s
xy = new int[N * N][2]; // 칸 번호
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
d[i] = Integer.parseInt(st.nextToken());
s[i] = Integer.parseInt(st.nextToken());
}
setxy(); // x,y좌표에 따른 칸 번호 생성
simulation();
System.out.println(res);
}
private static void setxy() { // x,y좌표에 따른 칸 번호 생성
int x = N / 2, y = N / 2;
int nx = 0, ny = 0;
int curDir = 3;
int d = 1; // 이동해야하는 양
int num = 1;
while (true) {
for (int k = 0; k < 2; k++) {
for (int i = 0; i < d; i++) {
if (x == 0 && y == 0)
return;
nx = x + dx[curDir];
ny = y + dy[curDir];
xy[num][0] = nx;
xy[num][1] = ny;
num++;
x = nx;
y = ny;
}
curDir = nextDir[curDir];
}
d++;
}
}
private static void simulation() {
for (int time = 0; time < M; time++) {
// 1. 현재 상어 위치에서 d 방향으로 s만큼 구슬 파괴시키기
breakRing(d[time], s[time]);
// 2. 구슬 파괴 후 빈칸 생긴 칸 기준으로 당기기
moveInside();
// 3. 같은거 4개 이상이면 폭발시키기
while (true) {
if (!bomb4()) // 더 이상 폭발시킬 것이 없을 경우
break;
else {
moveInside(); // 폭발 시켰으면 폭발 후, 이동
}
}
// 4. (그룹 개수, 그룹값) 2개로 쪼개기
split2();
}
}
private static void breakRing(int d, int s) { // 1. 현재 상어 위치에서 d 방향으로 s만큼 구슬 파괴시키기
int nx = N / 2, ny = N / 2;
for (int i = 0; i < s; i++) {
nx += dx[d];
ny += dy[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= N)
break;
map[nx][ny] = 0;
}
}
static int nextDir[] = { 0, 3, 4, 2, 1 }; // 다음 이동 방향
private static void moveInside() { // 2. 구슬 파괴 후 빈칸 생긴 칸 기준으로 당기기
for (int i = 1; i < N * N; i++) {
int cx = xy[i][0];
int cy = xy[i][1];
if (map[cx][cy] == 0) {
int[] nxy = find(i); // i보다 큰 것중에 0 아닌 값 찾기
int nx = nxy[0];
int ny = nxy[1];
map[cx][cy] = map[nx][ny];
map[nx][ny] = 0;
}
}
}
private static boolean bomb4() { // 연속되는 4개 터뜨리기.
int x = N / 2, y = N / 2; // 시작점
int nx = 0, ny = 0;
int curDir = 3; // 시작 방향
int d = 1; // 이동해야하는 양
int cnt = 0; // 연속으로 같은거 나오는 횟수
List<int[]> list = new ArrayList<>(); // 연속으로 같은거 나오는 좌표
boolean flag = false; // 폭발여부
while (true) {
if (x == 0 && y == 0) // (0,0) 도달하면 끝
break;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < d; i++) {
if (x == 0 && y == 0)
return flag;
nx = x + dx[curDir];
ny = y + dy[curDir];
if (cnt == 0 && map[x][y] != 0 && map[x][y] == map[nx][ny]) { // cnt=0일 때 map[x][y]==map[nx][ny]이면 cnt + 2 처리
cnt += 2;
list.add(new int[] { x, y });
list.add(new int[] { nx, ny });
} else if (cnt != 0 && map[x][y] != 0 && map[x][y] == map[nx][ny]) { // cnt >0인 경우, 계속 연속되고 있는 상황이기 때문에 map[nx][ny] 개수만 추가
cnt++;
list.add(new int[] { nx, ny });
}
if (map[x][y] != map[nx][ny]) { // 연속하지 않을 경우
if (cnt >= 4) { // 4개 이상 연속하면
flag = true; // 폭발 발생
for (int j = 0; j < list.size(); j++) {
int cur[] = list.get(j);
int cx = cur[0], cy = cur[1];
res += map[cx][cy];
map[cx][cy] = 0; // 폭발한 자리는 0으로 정리
}
}
cnt = 0; // cnt 변수 초기화
list.clear(); // 폭발할 x, y좌표 담는 리스트 초기화
}
x = nx; // 좌표 이동
y = ny;
}
curDir = nextDir[curDir];
}
d++;
}
return flag;
}
private static void split2() { // A그룹, B그룹으로 쪼개기
int newMap[][] = new int[N][N];
// map 탐색하면서 생긴 그룹들 newMap에 삽입.
int cnt = 1;
int num = 1;
int cx=0, cy =0, nx= 0, ny= 0;
for (int i = 1; i < N * N; i++) {
cx = xy[i][0];
cy = xy[i][1];
if(map[cx][cy]==0)
break;
if(i!=N*N-1) {
nx = xy[i + 1][0];
ny = xy[i + 1][1];
}
if (i!=N*N-1 && map[cx][cy] == map[nx][ny]) {
cnt++;
} else {
if(num>=N*N)
break;
int newx = xy[num][0];
int newy = xy[num][1];
num++;
if(num>=N*N)
break;
int newx2 = xy[num][0];
int newy2 = xy[num][1];
num++;
newMap[newx][newy] = cnt;
newMap[newx2][newy2] = map[cx][cy];
cnt = 1;
}
}
map = copy(newMap);
}
private static int[][] copy(int[][] map) {
int data[][] = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
data[i][j] = map[i][j];
}
return data;
}
private static int[] find(int num) { // 칸 번호에 해당하는 X, Y 좌표 반환
int nxy[] = new int[2];
for (int i = num + 1; i < N * N; i++) {
int cx = xy[i][0];
int cy = xy[i][1];
if (map[cx][cy] != 0) {
nxy[0] = cx;
nxy[1] = cy;
break;
}
}
return nxy;
}
}
🌟 비슷한 유형의 문제들
❗ 풀어보면 좋은 문제들
참고
