[백준] 21611 마법사 상어와 블리자드 - 구현(Implementation) + 시뮬레이션(Simulation) JAVA

passionfruit200 2023. 12. 5. 10:29

2023. 12. 5. 10:29

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;
    }
    
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 18429 근손실 - 백트래킹(Backtracking) + DFS(깊이우선탐색) + 일반순열(Normal Permutation) JAVA (0)	2023.12.06
[백준] 1189 컴백홈 - 백트래킹(Backtracking) + DFS(깊이우선탐색) JAVA (0)	2023.12.05
[백준] 17837 새로운 게임 2 - 구현(Implementation) + 시뮬레이션(Simulation) + 스택(Stack) JAVA (0)	2023.12.04
[백준] 17143 낚시왕 - 구현(Implementation) + 시뮬레이션(Simulation) JAVA (0)	2023.12.04
[백준] 1799 비숍 - 백트래킹(Backtracking) + DFS(깊이우선탐색) + 시간초과(TimeOut) JAVA (0)	2023.12.03

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200