https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
코드설명
구현(Implementation) + 시뮬레이션(Simulation) 를 활용하는 문제입니다.
문제를 한 문장으로 설명해보면, 주어진 판에서 상어가 블리자드 마법을 사용하여 시뮬레이션하고, 마법에 의해 일어나는 구슬의 변화를 처리하는 프로그램입니다.
코드의 큰 로직입니다. 자세한 사항은 모두 주석에 달아두었습니다. 또한 각 과정마다 모두 디버깅을 위해 출력과정을 담아두었습니다.
- 블리자드 마법 적용 (blizardMagic 함수):
- 주어진 방향과 거리에 따라 블리자드 마법을 시뮬레이션하여 Map에서 해당 위치의 구슬을 제거합니다.
- 빈 구슬 칸 채우기 (makeNewMap 함수):
- 구슬이 제거된 후 빈 공간을 제외한 나머지 구슬들을 상어와 가까운 칸에서 순서대로 떨어뜨려 채웁니다.
- 4개 이상 연속 구슬 폭파 (bombBallWhichIsLongerThan4 함수):
- Map을 순회하면서 4개 이상의 연속된 구슬이 있는 경우 폭파시킵니다.
- 각 그룹은 구슬의 개수와 번호로 큐에 저장되고, 나중에 처리됩니다.
- 구슬 변화 (mutateToNewBall 함수):
- 구슬 폭파 후 남은 구슬을 그룹화하여 구슬의 개수와 번호로 새로운 얼음판을 만듭니다.
- 얼음판을 중앙에서 시작하여 반시계방향으로 탐색하며 변화를 적용합니다.
- 결과 출력:
- 마법을 여러 번 시뮬레이션한 후 각 색의 구슬이 폭발한 횟수를 계산하여 출력합니다.
유의해야할점입니다.
첫번째는, 구슬의 개수를 셀때, 마지막에도 세주어야합니다. 처음에 94%에서 틀려서 원인을 찾아보니 마지막에 칸에서 벗어날때도 개수를 세주어야합니다.
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(map[r][c] != EMPTY_SPACE) {
//만약 연속적인 볼과 다르다면,
if(continuousBallNumber != map[r][c]) {
//만약 다른데 갯수가 4개 이상이라면, 해당 큐는 새로운 큐에 들어가지 못한다. 즉 폭파한다는 뜻이다.
if(continuousCnt >= 4) {
answer[continuousBallNumber] += continuousCnt;
findFlag = true;
continuousCheckQ.clear();
}
//만약 4개 이하라면, 이전 큐에 넣어줍니다.
else if(continuousCnt < 4) {
while(!continuousCheckQ.isEmpty()) {
q.offer(continuousCheckQ.poll());
}
}
continuousCnt = 1;
continuousBallNumber = map[r][c];
}
//연속적인 볼이라면 갯수를 증가시킨다.
else if(continuousBallNumber == map[r][c]) { //만약 이전 값과 같다면, 연속적인 볼이라면 하나씩 세어줍니다.
continuousCnt += 1;
}
continuousCheckQ.offer(map[r][c]); //먼저 넣는다.
}
}
}
level += 1;
}
//만약 다른데 갯수가 4개 이상이라면, 해당 큐는 새로운 큐에 들어가지 못한다.
if(continuousCnt >= 4) {
answer[continuousBallNumber] += continuousCnt;
findFlag = true;
continuousCheckQ.clear();
}
두번쨰는, 반시계방향으로 순회하는것에 대한 로직입니다.
이 사항은 유의해야할점이라기보다는 이 문제 구현에 있어서 가장 중요한 코드이기에 읽어보면 좋습니다.
//반시계방향으로 순회.
public static void traverseByAntiColor() {
int level = 1;
int dir = 0; //처음에는 왼쪽방향부터 시작합니다.
int r = (N/2); int c = (N/2);
int nr = r; int nc = c;
int moveCnt = 1;
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
System.out.print(" "+map[r][c]);
}
System.out.println(" ");
}
level += 1;
}
}
세번째, 각 코드를 안에서부터 채워나갈떄 하나의 Map안에서 땡긴다기보다는 Queue를 활용해서 새로운 newMap을 반환시켜 한다면 편하게 구현할 수 있는 것 같습니다. 여러 풀이가 있지만, 저는 그렇습니다.
처음에는 DFS로 구현하는것도 생각해봤었는데 이렇게 For문으로 구현하는것이 훨씬 편한것 같습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[][] map;
public static int[] answer = new int[4];
public static int[] dx = {-1, 1, 0, 0};
public static int[] dy = {0, 0, -1, 1};
public static int EMPTY_SPACE = 0;
public static boolean bombBallWhichIsLongerThan4Flag = false;
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];
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());
// System.out.print(" "+map[i][j]);
}
// System.out.println();
}
// System.out.println();
//
for(int i=0; i<M;i++) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
//마법이 주어지고, 일련의 과정이 진행된다.
//이거 굳이 떙기지않고, 새로 만들어서 하나씩 채워가는것이 훨씬 편할것이다.
//1. 마법에 의해 얼음파편이 떨어져 구슬이 파괴된다.
blizardMagic(d - 1, s);
// System.out.println("blizard Magic ==================================");
// for(int k=0;k<N;k++) {
// for(int h=0;h<N;h++) {
// System.out.print(" "+map[k][h]);
// }
// System.out.println();
// }
// System.out.println();
//2. 빈 구슬칸을 채워준다.
// System.out.println("makeNew Map ==================================");
map = makeNewMap();
// for(int k=0;k<N;k++) {
// for(int h=0;h<N;h++) {
// System.out.print(" "+map[k][h]);
// }
// System.out.println();
// }
// System.out.println();
bombBallWhichIsLongerThan4Flag = false;
//3. 4개이상 연속하는 구슬이있을경우 구슬이 4개 이상의 구슬이 모두 폭파된다.
while(bombBallWhichIsLongerThan4Flag == false) {
map = bombBallWhichIsLongerThan4();
// System.out.println("bombBallWhichIsLongerThan4 Map ==================================");
// for(int k=0;k<N;k++) {
// for(int h=0;h<N;h++) {
// System.out.print(" "+map[k][h]);
// }
// System.out.println();
// }
// System.out.println();
}
//4. 더이상 폭발할 구슬이 없다면, 구슬이 변화하는 단계가 된다. 연속하는 구슬은 하나의 그룹이라고한다.
// 하나의 그룹은 두개의 구슬 A와 B로 변화한다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이다. B는 그룹을 이루고 있는 구슬의 번호이다.
// 구슬은 다시 구슬의 순서대로 1번칸부터 차례대로 A, B의 순서로 칸에 들어간다.
map = mutateToNewBall();
// System.out.println("mutateToNewBall Map ==================================");
// for(int k=0;k<N;k++) {
// for(int h=0;h<N;h++) {
// System.out.print(" "+map[k][h]);
// }
// System.out.println();
// }
// System.out.println();
}
// System.out.println(answer[0]);
System.out.println(answer[1] * 1 + answer[2] * 2 + answer[3] * 3);
// traverseByAntiColor();
}
//4개 이상 연속 구슬이 있을시에 구슬이 폭발한다.
public static int[][] mutateToNewBall() {
Queue<Integer> q = new LinkedList<>();
Queue<Integer> continuousCheckQ = new LinkedList<>();
int level = 1;
int dir = 0; //처음에는 왼쪽방향부터 시작합니다.
int r = (N/2); int c = (N/2);
int moveCnt = 1;
//연속적인 볼의 개수의 변수명.
//먼저 기존 얼음판을 빈칸으 빼고 복사해옵니다.
int continuousCnt = 0;
int continuousBallNumber = EMPTY_SPACE; //어처피 이전에 블리자드로 구슬이 파괴된 후에 구슬이 다시 채워지니 빈칸은 걱정안해도 될듯하다.
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(map[r][c] != EMPTY_SPACE) {
//만약 연속적인 볼과 다르다면,
if(continuousBallNumber != map[r][c]) {
//만약 다르다면, continuousQ에 (그룹의 개수, 구슬의 번호) 를 차례대로(순서지켜야한다) 넣는다.
if(continuousBallNumber != EMPTY_SPACE) {
continuousCheckQ.offer(continuousCnt);
continuousCheckQ.offer(continuousBallNumber);
//먼저 값을 넣어야한다. (맨 처음값같은경우는 어처피 값이 안들어가므로 상관없다.)
while(!continuousCheckQ.isEmpty()) {
q.offer(continuousCheckQ.poll());
}
}
continuousCnt = 1;
continuousBallNumber = map[r][c];
}
//연속적인 볼이라면 갯수를 증가시킨다.
else if(continuousBallNumber == map[r][c]) { //만약 이전 값과 같다면, 연속적인 볼이라면 하나씩 세어줍니다.
continuousCnt += 1;
}
}
}
}
level += 1;
}
continuousCheckQ.offer(continuousCnt);
continuousCheckQ.offer(continuousBallNumber);
//먼저 값을 넣어야한다. (맨 처음값같은경우는 어처피 값이 안들어가므로 상관없다.)
while(!continuousCheckQ.isEmpty()) {
q.offer(continuousCheckQ.poll());
}
int[][] newMap = new int[N][N];
level = 1;
dir = 0; //처음에는 왼쪽방향부터 시작합니다.
r = (N/2); c = (N/2);
moveCnt = 1;
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(q.isEmpty()) return newMap;
newMap[r][c] = q.poll();
}
}
level += 1;
}
return newMap;
}
public static void blizardMagic(int d, int s) {
int r = (N/2), c = (N/2);
for(int i=0; i<s;i++) {
r = r + dx[d];
c = c + dy[d];
//문제어 주어진 S는 (N-1)/2 이기에 범위 걱정없다.
map[r][c] = EMPTY_SPACE;
}
}
public static int[][] makeNewMap(){
Queue<Integer> q = new LinkedList<>();
int level = 1;
int dir = 0; //처음에는 왼쪽방향부터 시작합니다.
int r = (N/2); int c = (N/2);
int moveCnt = 1;
//먼저 기존 얼음판을 빈칸으 빼고 복사해옵니다.
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(map[r][c] != EMPTY_SPACE) q.offer(map[r][c]);
}
}
level += 1;
}
int[][] newMap = new int[N][N];
level = 1;
dir = 0; //처음에는 왼쪽방향부터 시작합니다.
r = (N/2); c = (N/2);
moveCnt = 1;
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(q.isEmpty()) return newMap;
newMap[r][c] = q.poll();
}
}
level += 1;
}
return newMap;
}
//4개 이상 연속 구슬이 있을시에 구슬이 폭발한다.
public static int[][] bombBallWhichIsLongerThan4() {
Queue<Integer> q = new LinkedList<>();
Queue<Integer> continuousCheckQ = new LinkedList<>();
int level = 1;
int dir = 0; //처음에는 왼쪽방향부터 시작합니다.
int r = (N/2); int c = (N/2);
int moveCnt = 1;
//연속적인 볼의 개수의 변수명.
//먼저 기존 얼음판을 빈칸으 빼고 복사해옵니다.
int continuousCnt = 0;
int continuousBallNumber = EMPTY_SPACE; //어처피 이전에 블리자드로 구슬이 파괴된 후에 구슬이 다시 채워지니 빈칸은 걱정안해도 될듯하다.
boolean findFlag = false;
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(map[r][c] != EMPTY_SPACE) {
//만약 연속적인 볼과 다르다면,
if(continuousBallNumber != map[r][c]) {
//만약 다른데 갯수가 4개 이상이라면, 해당 큐는 새로운 큐에 들어가지 못한다. 즉 폭파한다는 뜻이다.
if(continuousCnt >= 4) {
answer[continuousBallNumber] += continuousCnt;
findFlag = true;
continuousCheckQ.clear();
}
//만약 4개 이하라면, 이전 큐에 넣어줍니다.
else if(continuousCnt < 4) {
while(!continuousCheckQ.isEmpty()) {
q.offer(continuousCheckQ.poll());
}
}
continuousCnt = 1;
continuousBallNumber = map[r][c];
}
//연속적인 볼이라면 갯수를 증가시킨다.
else if(continuousBallNumber == map[r][c]) { //만약 이전 값과 같다면, 연속적인 볼이라면 하나씩 세어줍니다.
continuousCnt += 1;
}
continuousCheckQ.offer(map[r][c]); //먼저 넣는다.
}
}
}
level += 1;
}
//만약 다른데 갯수가 4개 이상이라면, 해당 큐는 새로운 큐에 들어가지 못한다.
if(continuousCnt >= 4) {
answer[continuousBallNumber] += continuousCnt;
findFlag = true;
continuousCheckQ.clear();
}
//만약 4개 이하라면, 이전 큐에 넣어줍니다.
else if(continuousCnt < 4) {
while(!continuousCheckQ.isEmpty()) {
q.offer(continuousCheckQ.poll());
}
}
if(findFlag == false) {
bombBallWhichIsLongerThan4Flag = true;
return map;
}
int[][] newMap = new int[N][N];
level = 1;
dir = 0; //처음에는 왼쪽방향부터 시작합니다.
r = (N/2); c = (N/2);
moveCnt = 1;
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
if(q.isEmpty()) return newMap;
newMap[r][c] = q.poll();
}
}
level += 1;
}
return newMap;
}
//반시계방향으로 순회.
public static void traverseByAntiColor() {
int level = 1;
int dir = 0; //처음에는 왼쪽방향부터 시작합니다.
int r = (N/2); int c = (N/2);
int nr = r; int nc = c;
int moveCnt = 1;
while(level <= N) {
//각 2번씩 같은숫자만큼 방향을 바꿔가며 이동한다.
for(int turn = 0; turn < 2; turn ++) {
dir = changeDir(dir);
//level만큼 이동한다. level, level, level + 1, level + 1 ... 의 규칙성이 존재한다.
for(int move = 0 ; move < level; move ++) {
r = r + dx[dir]; //이동
c = c + dy[dir];
moveCnt += 1;
if(r < 0 || r > N || c < 0 || c > N) continue;
System.out.print(" "+map[r][c]);
}
System.out.println(" ");
}
level += 1;
}
}
public static int changeDir(int dir) {
if(dir == 0) {
return 2;
}else if(dir == 1) {
return 3;
}else if(dir == 2) {
return 1;
}else if(dir == 3) {
return 0;
}
//여기까지 올일은없음.
return -1;
}
}