문제
- 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이며 마법사 상어는 ((N+1)/2, (N+1)/2)에 있다.
가장 처음에 상어가 있는 칸을 제외한 나머지 칸에는 구슬이 하나 들어갈 수 있다. 구슬은 1번 구슬, 2번 구슬, 3번 구슬이 있다. 같은 번호를 가진 구슬이 번호가 연속하는 칸에 있으면, 그 구슬을 연속하는 구슬이라고 한다. 다음은 N = 7인 경우 예시이다. 블리자드 마법을 시전하려면 방향 di와 거리 si를 정해야 한다. 총 4가지 방향 ↑, ↓, ←, →가 있고, 정수 1, 2, 3, 4로 나타낸다. 상어는 di 방향으로 거리가 si 이하인 모든 칸에 얼음 파편을 던져 그 칸에 있는 구슬을 모두 파괴한다. 구슬이 파괴되면 그 칸은 구슬이 들어있지 않은 빈 칸이 된다. 얼음 파편은 벽의 위로 떨어지기 때문에, 벽은 파괴되지 않는다.
N = 3 N = 5 N = 7 만약 어떤 칸 A의 번호보다 번호가 하나 작은 칸이 빈 칸이면, A에 있는 구슬은 그 빈 칸으로 이동한다. 이 이동은 더 이상 구슬이 이동하지 않을 때까지 반복된다. 따라서, 구슬이 파괴된 후에는 빈 칸이 생겨 구슬이 이동하고, 구슬이 모두 이동한 결과는 다음과 같다.이제 구슬이 폭발하는 단계이다. 폭발하는 구슬은 4개 이상 연속하는 구슬이 있을 때 발생한다. 다음은 왼쪽 그림은 위의 상태에서 폭발하는 구슬이 들어있는 칸을 파란색과 초록색으로 표시한 것이고, 오른쪽 그림은 구슬이 폭발한 후의 상태이다.빨간색으로 표시된 칸에 얼음 파편이 떨어진다. 구슬이 파괴된 후 구슬이 폭발해 빈 칸이 생겼으니 다시 구슬이 이동한다. 구슬이 이동한 후에는 다시 구슬이 폭발하는 단계이고, 이 과정은 더 이상 폭발하는 구슬이 없을때까지 반복된다. 구슬이 폭발한 후의 상태에서 구슬이 이동하면 다음과 같다.위의 상태는 4개 이상 연속하는 구슬이 있기 때문에 구슬이 다시 폭발하게 된다.구슬이 폭발하기 전 구슬이 폭발한 후 이제 더 이상 폭발한 구슬이 없기 때문에, 구슬이 변화하는 단계가 된다. 연속하는 구슬은 하나의 그룹이라고 한다. 다음은 1번 구슬은 빨간색, 2번 구슬은 파란색, 3번 구슬은 보라색으로 표시한 그림이다.하나의 그룹은 두 개의 구슬 A와 B로 변한다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이고, B는 그룹을 이루고 있는 구슬의 번호이다. 구슬은 다시 그룹의 순서대로 1번 칸부터 차례대로 A, B의 순서로 칸에 들어간다. 다음 그림은 구슬이 변화한 후이고, 색은 구분하기 위해 위의 그림에 있는 그룹의 색을 그대로 사용했다. 만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다.마법사 상어는 블리자드를 총 M번 시전했다. 시전한 마법의 정보가 주어졌을 때, 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 구해보자.구슬이 폭발하기 전 구슬이 폭발하고 이동한 후 -
- 다음 예시는 방향은 아래, 거리는 2인 경우이다.
- 일부 칸과 칸 사이에는 벽이 세워져 있으며, 다음은 N = 3, 5, 7인 경우의 예시이다. 실선은 벽이고, 점선은 벽이 아니다. 칸에 적혀있는 수는 칸의 번호이다.
- 출력
- 첫째 줄에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력한다.
- 입력
- 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 격자에 들어있는 구슬의 정보가 주어진다. r번째 행의 c번째 정수는 (r, c)에 들어있는 구슬의 번호를 의미한다. 어떤 칸에 구슬이 없으면 0이 주어진다. 상어가 있는 칸도 항상 0이 주어진다.
- 다음 M개의 줄에는 블리자드 마법의 방향 di와 거리 si가 한 줄에 하나씩 마법을 시전한 순서대로 주어진다.
M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
입력
첫째 줄에 N, M이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.
다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.
출력
첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.
🌈 풀이 후기 (시뮬레이션)
- 한시간 정도 걸렸던것 같다. 이 문제를 풀때는 List를 만들어줘서 구슬의 빈칸을 제외하고 채워주면서 붙어있는 개수를 비교해줬다.
- 이 문제도 작년 문제인 파이어스톰? 문제와 비슷해서 접근하기 쉬웠다.
👩🏫 문제 풀이
문제의 핵심은 크게 2가지,
1. 코너를 두번 돌때마다 반복횟수가 1 증가한다는 점과 반복횟수만큼 이동했으면 방향이 바뀐다는점을 잘 이용해주면 된다.
2. 폭발한 구슬로 인해 연속된 값을 비교하기 힘들었다. 이를 위해 list에 하나씩 집어 넣으면서 연속되는지 확인해준다.
연속 된다면 연속된 구슬을 터트리고 비교해준다. 이때는 리스트가 앞으로 땡겨지기 때문에 뒤에서부터 터트려줬다.
한번이라도 터트렸다면 구슬이 이동해서 연속되는 값이 생길수 있기에 한번 더 체크해준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N, M, mid;
static int[][] map;
static int[][] attack;
static List<Integer> list;
static int dr[] = { 0, -1, 1, 0, 0 }; // 상하좌우
static int dc[] = { 0, 0, 0, -1, 1 };
static int sum = 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][N];
attack = new int[M][2];
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());
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
attack[i][0] = Integer.parseInt(st.nextToken()); // d
attack[i][1] = Integer.parseInt(st.nextToken()); // s
}
mid = N / 2;
list = new ArrayList<Integer>();
for (int i = 0; i < M; i++) {
int d = attack[i][0];
int s = attack[i][1];
list.clear();
attack(d, s);
move();
remove();
map = new int[N][N];
divide();
}
System.out.println(sum);
}
private static void divide() {
ArrayList<Integer> newList = new ArrayList<Integer>();
int size = list.size();
int connectCnt = 1;
for (int i = 0; i < size - 1; i++) {
if (list.get(i) == list.get(i + 1)) {
connectCnt++;
} else {
newList.add(connectCnt);
newList.add(list.get(i));
connectCnt = 1;
}
}
// 마지막처리
if(size >=1) {
newList.add(connectCnt);
newList.add(list.get(size - 1));
}
// add
int cnt = 0;
size = 1;
int corner = 0;
int dir = 3; // 좌시작
int nr = mid;
int nc = mid;
int time = newList.size();
int total=0;
while (time-- > 0) {
cnt++;
nr += dr[dir];
nc += dc[dir];
if (nr == 0 && nc == -1)
break;
// list에 넣기
map[nr][nc] = newList.get(total++);
// 반복횟수만큼 갔으면 다음 방향으로 변경
if (cnt == size) {
corner++;
dir=dirChange(dir);
// 3 2 4 1
cnt = 0;
}
// 코너를 2번 돌때마다 반복횟수 1 증가
if (corner == 2) {
corner = 0;
size++;
}
}
}
private static int dirChange(int d) {
if(d==3)
return 2;
else if(d==2)
return 4;
else if(d==4)
return 1;
else if(d==1)
return 3;
return 0;
}
private static void remove() {
int[][] removeList = new int[650][2];
int size = list.size();
int connectCnt = 1;
int removeCnt = 0;
boolean isRemove = false;
for (int i = 0; i < size - 1; i++) {
if (list.get(i) == list.get(i + 1)) {
connectCnt++;
} else {
if (connectCnt >= 4) {
removeList[removeCnt][0] = i - connectCnt + 1;
removeList[removeCnt][1] = connectCnt;
removeCnt++;
isRemove = true;
}
connectCnt = 1;
}
}
// 마지막 처리
if (connectCnt >= 4) {
removeList[removeCnt][0] = size - connectCnt;
removeList[removeCnt][1] = connectCnt;
removeCnt++;
isRemove = true;
}
if (isRemove) {
for (int k = removeCnt - 1; k >= 0; k--) {
int start = removeList[k][0];
int len = removeList[k][1];
for (int i = 0; i < len; i++) {
sum += list.get(start);
list.remove(start);
}
}
}
if (isRemove) {
remove();
}
}
private static void move() {
int cnt = 0;
int size = 1;
int corner = 0;
int dir = 3; // 좌시작
int nr = mid;
int nc = mid;
while (true) {
cnt++;
nr += dr[dir];
nc += dc[dir];
if (nr == 0 && nc == -1)
break;
// list에 넣기
if (map[nr][nc] != 0)
list.add(map[nr][nc]);
// 반복횟수만큼 갔으면 다음 방향으로 변경
if (cnt == size) {
corner++;
dir=dirChange(dir);
cnt = 0;
}
// 코너를 2번 돌때마다 반복횟수 1 증가
if (corner == 2) {
corner = 0;
size++;
}
}
}
private static void attack(int d, int s) {
for (int i = 1; i <= s; i++) {
int nr = mid + dr[d] * i;
int nc = mid + dc[d] * i;
if (canMove(nr, nc)) {
// sum += map[nr][nc]; // 시험에서는 이것도 점수
map[nr][nc] = 0;
} else
break;
}
}
private static boolean canMove(int r, int c) {
return (r >= 0 && c >= 0 && r < N && c < N);
}
}'Algorithm(알고리즘) > Java' 카테고리의 다른 글
| [Java][백준 1522][문자열] 문자열 교환 (0) | 2021.07.06 |
|---|---|
| [Java][백준 21610][시뮬레이션][삼성SW 역량 테스트] 마법사 상어와 비바라기 (0) | 2021.05.26 |
| [Java][백준 13460][BFS+시뮬레이션][삼성SW 역량 테스트] 구슬탈출 2 (0) | 2021.04.22 |
| [Java][백준 20056][시뮬레이션][삼성SW 역량 테스트] 마법사 상어와 파이어볼 (0) | 2021.04.15 |
| [Java][백준 1254][팰린드롬] 팰린드롬 만들기 (1) | 2021.04.07 |