- 소요시간 : 2시간 20분
- 문제 사이트 : 백준
- 문제 수준 : 골드 1
- 문제 유형 : 구현, 시뮬레이션
- 다른 사람의 풀이를 참고 했는가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/21611
- 푼 날짜 : 2023.05.07
1. 사용한 자료구조 & 알고리즘
구현, 시뮬레이션
2. 사고과정
문제 보자마자 빡구현 문제라고 생각
1. 구슬들이 이동하는 경로를 어떻게 구현할 것인가?
맵에서 구슬들이 이동하는 경로가
문제와 똑같았음. 그래서 이 당시에 토네이도를 구했던 방법을 떠올려서 응용함. 당시 문제를 푼 것은
에 있음. 그래서 먼저 토네이도가 이동하는 좌표를 ArrayList에 담았음.
사실 토네이도 좌표를 순서대로 구했다면 30% 정도 성공한 것. 구슬들이 이동할 때나, 연속으로 이어지는 구슬들이 있나 체크할 때 이 좌표를 많이 활용함.
2. 연속으로 이어지는 4개 이상의 구슬을 어떻게 알아낼 것인가?
-> 구슬들이 이동하는 경로를 구했으니, 가운데 좌표(상어가 아닌)에서부터 하나하나 구슬들을 보면서 이전 구슬 번호와 현재 구슬 번호를 보면서 비교했음.
3. 구슬들이 제거된 후, 구슬들을 어떻게 앞당길 것인가?
-> 이것도 구슬들이 이동하는 경로를 알고 있으니, 앞에서부터 차례대로 0이 아닌 구슬 번호들을 담고, 맵을 0으로 초기화. 그 후, 다시 가운데 좌표에서 부터, 담았던 구슬 번호들을 차례대로 지정.
3. 풀이과정
- d방향으로 s만큼의 구슬을 제거
- 구슬들이 사라졌으니 구슬들을 이동시킴
- 4개이상 이어지는 구슬이 있나 체크, 있다다면 구슬들을 제거하면서 sum에 더함
- 구슬들이 사라지며 생긴 빈 공간을 메꿈. 4개 이상 이어지는 구슬이 없을 때까지 3 ~ 4 반복
- 연속되는 번호의 구슬, 개수에 따라서 맵을 재배치 한다.
4. 소스코드
import java.util.*;
import java.io.*;
public class Main{
static int yy[] = {-1,1,0,0};
static int xx[] = {0,0,-1,1};
static ArrayList<Integer[]> movingWay=new ArrayList<>();
static int sum = 0;
static int marble[][];
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int M=Integer.parseInt(st.nextToken());
marble=new int[N][N];
for(int i=0;i<marble.length;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<marble.length;j++) {
marble[i][j] = Integer.parseInt(st.nextToken());
}
}
//토네이도의 좌표를 구해서 ArrayList에 담는다.
calculateTonado();
for(int i=0;i<M;i++) {
st=new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
//해당 방향의 구슬을 제거한다.
remove(d-1,s);
//구슬을 이동시킨다.
moveMarble();
//4개 이상 이어지는 구슬이 있는지 확인하고
//있다면 구슬을 이동시킨다.
while(checkMarble())
moveMarble();
//이어지는 구슬의 번호, 개수에 따라서 구슬을 재배치한다.
changeMarble();
}
System.out.println(sum);
}
//가운를 기준으로 해당 방향의 구슬을 제거한다.
//제거한 것은 0으로 표시
public static void remove(int d,int s) {
int nowY = marble.length/2;
int nowX = marble.length/2;
for(int i=0;i<s;i++) {
int nextY = nowY+yy[d];
int nextX = nowX+xx[d];
marble[nextY][nextX] = 0;
nowY=nextY;
nowX=nextX;
}
}
//구슬을 이동시킨다.
public static void moveMarble() {
Queue<Integer> queue=new LinkedList<>();
//처음에 구해놓은 토네이도의 좌표를 활용
//1이상의 구슬 번호를 가진 구슬을 순서대로 저장.
for(int i=0;i<movingWay.size();i++) {
Integer temp[]= movingWay.get(i);
int y = temp[0];
int x = temp[1];
if(marble[y][x]!=0)
queue.add(marble[y][x]);
}
//구슬은 전부 0으로 처리한 후
for(int i=0;i<marble.length;i++) {
for(int j=0;j<marble.length;j++) {
marble[i][j] = 0;
}
}
int idx = 0;
//다시 처음부터 저장한 구슬들을 배치
while(!queue.isEmpty()) {
int number=queue.poll();
int y = movingWay.get(idx)[0];
int x = movingWay.get(idx++)[1];
marble[y][x] = number;
}
}
//4개이상 이어지는 구슬이 있는지 확인함.
public static boolean checkMarble() {
Queue<Integer[]> temp=new LinkedList<>();
Queue<Integer[]> removeList = new LinkedList<>();
boolean find = false;
int y = movingWay.get(0)[0];
int x = movingWay.get(0)[1];
int number=marble[y][x];
int combo = 1;
temp.add(new Integer[] {y,x});
//combo로 이어지는 구슬의 개수를 판별함.
for(int i=1;i<movingWay.size();i++) {
int nowY=movingWay.get(i)[0];
int nowX=movingWay.get(i)[1];
//구슬이 없다면 break
if(marble[nowY][nowX]==0) break;
//이전 구슬과 다음 구슬의 번호가 같다면 콤보 증가
if(marble[nowY][nowX] == number) {
combo++;
temp.add(new Integer[] {nowY,nowX});
}
//구슬의 번호가 다르다면
else {
//콤보가 4이상이라면 파괴할 구슬을 찾은 것. find가 true가 됨
if(combo>=4) {
find = true;
//제거해야할 list에 담음.
while(!temp.isEmpty())
removeList.add(temp.poll());
}
//기준 번호는 현재 구슬 번호, 콤보는 1이 됨.
number = marble[nowY][nowX];
combo = 1;
temp.clear();
temp.add(new Integer[] {nowY,nowX});
}
}
//맨 마지막에 콤보가 4 이상인 채로 맵 밖을 나왔을 때의 예외 처리.
//구슬 번호가 달라지지 않은 채로 4 이상의 콤보가 나온 후, 0,0의 좌표를 만나 맵 밖을 나온 경우 처리
if(combo>=4) {
find = true;
while(!temp.isEmpty())
removeList.add(temp.poll());
}
//제거해야할 구슬들의 좌표에 해당하는 구슬들을 없앰
//구슬 번호에 따라서 sum 증가.
while(!removeList.isEmpty()) {
Integer poll[]=removeList.poll();
int nowY=poll[0];
int nowX=poll[1];
switch(marble[nowY][nowX]) {
case 1: sum += marble[nowY][nowX]; break;
case 2: sum += marble[nowY][nowX]; break;
case 3: sum += marble[nowY][nowX]; break;
}
marble[nowY][nowX] = 0;
}
return find;
}
//구슬들을 재배치함
public static void changeMarble() {
Queue<Integer[]> queue=new LinkedList<>();
int y = movingWay.get(0)[0];
int x = movingWay.get(0)[1];
int number=marble[y][x];
int combo = 1;
//이어지는 구슬이 나와 번호가 같나 체크.
for(int i=1;i<movingWay.size();i++) {
Integer temp[]= movingWay.get(i);
int nowY=temp[0];
int nowX=temp[1];
//0을 만나면 break
if(marble[nowY][nowX]==0) {
if(number!=0)
queue.add(new Integer[] {combo,number});
break;
}
//이전 구슬 번호와 다음 구슬 번호가 같다면 콤보 증가
if(marble[nowY][nowX] == number) {
combo++;
}
//다르다면 queue에 콤보와, 구슬 번호를 저장함.
//구슬 번호, 콤보 다시 세팅
else {
queue.add(new Integer[] {combo,number});
number=marble[nowY][nowX];
combo = 1;
}
}
if(queue.size()==0&&combo==1) {
if(number!=0)
queue.add(new Integer[] {combo,number});
}
//맵 전체의 구슬을 0으로 초기화
for(int i=0;i<marble.length;i++) {
for(int j=0;j<marble.length;j++) {
marble[i][j] = 0;
}
}
//queue에 담아 놓은 콤보와 구슬 번호들로 map을 재배치.
for(int i=0;i<movingWay.size();i+=2) {
Integer temp1[]= movingWay.get(i);
Integer temp2[]= movingWay.get(i+1);
int nowY1=temp1[0];
int nowX1=temp1[1];
int nowY2=temp2[0];
int nowX2=temp2[1];
if(queue.size()==0) break;
Integer temp[] = queue.poll();
int tempCombo=temp[0];
int tempNumber=temp[1];
marble[nowY1][nowX1] = tempCombo;
marble[nowY2][nowX2] = tempNumber;
}
}
//토네이도를 구함
//이전에 '마법사 상어와 토네이도' 문제에서 토네이도를 구했던 방법을 떠올려서 활용했음
public static void calculateTonado() {
int tonadoY[] = {0,1,0,-1};
int tonadoX[] = {-1,0,1,0};
Queue<Integer[]> queue=new LinkedList<>();
queue.add(new Integer[] {marble.length/2,marble.length/2,0,0});
int count = 0;
while(true) {
Integer temp[]= queue.poll();
int nowY=temp[0];
int nowX=temp[1];
int dir = temp[2];
int cycle=temp[3];
if(count%2==0)
cycle++;
count ++;
for(int i=0;i<cycle;i++) {
int nextY = nowY+tonadoY[dir];
int nextX = nowX+tonadoX[dir];
movingWay.add(new Integer[] {nextY,nextX});
if(nextY==0&&nextX==0)
return;
nowY=nextY;
nowX=nextX;
}
dir++;
dir%=4;
queue.add(new Integer[] {nowY,nowX,dir,cycle});
}
}
}
5. 결과
2시간째 풀었을 때 제출 했는데 틀렸다고 뜸.
65% 정도에서 틀려서 이거 고치느라 애먹었음
각 과정을 거칠 때마다 하나씩 출력해보니
맵이 0으로 다 덮여있을 때에도 구슬이 재배치 됐을 때
기본 combo를 1로 잡았으므로, combo 1로 구슬번호 0이 맵에 배치되는 현상 발생.
그래서 구슬을 재배치하는 메소드에서 queue의 size()가 0이라면 break 해주는 메소드를 추가함으로써 해결!
6. 회고
토네이도 문제를 풀지 않았더라면, 그 방법까지 다시 생각했어야 했으므로 2시간 20분보다 20~30분 더 걸렸을 것 같다.
이전에 풀었던 문제들을 응용해서 문제를 푼다는 것이, 역시 문제를 많이 풀어보는게 도움이 된다고 느꼈다.
200줄 이상의 코드를 짜는 것이 익숙해지다 보니
처음에는 100줄 이상만 돼도 문제 참... 하면서 생각했는데
이제는 거리감이 없어졌다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
학습된 낭만