[시뮬레이션] 2차원 배열에서 Bomb? Down!

 

 

안녕하세요 여러분 우기의 취준일기입니다. 이제 간단한 Tip 게시판에 우리가 헷갈리거나 공부를 해야할만한 알고리즘 유형들을 갖고오겠습니다 !!! 그런의미로 시뮬레이션 문제 유형에서 폭탄이 터지거나 중력에 의해 끌려오는걸 항상 접해봤었죠...? 그런 유형들을 어떻게 극복하고 해결하는지 알아보겠습니다 ~~

 

❤ 빨리 이해해봐요!

1. 폭탄이 어떻게 터지는지 유형을 파악해봐요

2. 터트린 폭탄을 어떻게 밑으로 내려서 정리할지 생각해봐요~!

 

쉽게 풀려면 이렇게만 생각해보는게 맞지만...! 우리는 좀 더 Deep 하게 풀어봐야겠죠? 

 

먼저 폭탄이 터지는 유형을 공부하고, 그 다음 어떻게 폭탄을 내릴지 고민해봅시다~!

 

❤. 폭탄이 터지는 대표적인 유형

🧡. 폭탄이 십자가로 터지는 경우

폭탄이 십자가로 터지는 경우

 

이때는 터지는 범위를 먼저 떠올라야합니다. 폭탄의 상하좌우가 1초마다 점점 넓어진다는 전제하에 생각해보겠습니다. 그렇다면 맨허튼 거리를 떠올리면 어떨까요? 왜 맨허튼 거리를 떠올려야 하나요? 라는 생각이 들수 있습니다.

그 이유는 바로 폭탄이 있는 중점에서 각 방향의 끝점과의 거리를 계산하여 폭탄의 위치를 알아야 하기때문입니다.

즉, 맨해튼 거리는 폭탄의 거리라는것이죠  

그러나 맨해튼 거리는 폭탄의 거리보다 작다는걸 이용할수있습니다. 코드로 보시죠

 return (x == centerX || y == centerY) &&

               Math.abs(x - centerX) + Math.abs(y - centerY) < bombRange;

 

즉 이런 값을통해서 중심좌표만 알수있다면 터지는 범위의 크기를 인지할수 있습니다. 

 

 

🧡. 폭탄이 연쇄적으로 터지는 경우

 

일정 길이만큼의 폭탄이 터지는 경우

이 경우는 폭탄의 범위가 3 이상이라면 해당 범위중 나열된 폭탄은 모두 터지는 유형입니다. 그렇다면 주어진 시작점에 부분 수열의 끝 위치를 알아보면 어떨까요...?

 

만일 (N-1,0)에 있는 노란색 B부터 검사해볼까요...? 

int endIdx = startIdx + 1;

        while(endIdx < endOfArray) {

            if(numbers[endIdx] == currNum)

                endIdx++;

            else{

                break;

            }

        }

   

        return endIdx - 1;

 

endIdx을 이용하여 수열에 해당하는 값을 계속 비교하여 폭탄 범위를 넘어가면 해당 Idx값을 주는 방식을 사용하면됩니다.

 

자 이제 대표적인 2개의 유형을 알아봤으면 중력으로 떨어트리는 방법만 알면 해결됩니다...!

 

❤. 중력으로 폭탄을 떨어트리기 !

🧡. 임시 배열 생성하기

 

왼쪽은 폭탄이 터진후, 오른쪽은 임시 배열...!

 

폭탄이 십자가 형태로 터졌습니다...! 하지만 다음상황을위해 폭탄을 중력으로 떨어트려야 합니다. 원본배열을 사용하기에는 너무 복잡해보입니다... 우리는 잠시 폭탄들을 임시로 중력으로 갖다놓을 임시배열을 만드는것이 첫번째 방법입니다. 

 

🧡. 임시 인덱스를 생성하기 

 

 

2차원 배열에서 중력으로 끌기위해선 아래에서 위로 올라가야합니다.

1. Row값을 증가시키며 값을 확인합니다.

2. 빈값이라면 tempRow 증가도, 임시 배열의 빈칸도 채우지 않습니다.

3. 빈칸이 아니라면 Row의 값을 임시배열의 값으로 넣고, tempRow 인덱스또한 증가시킵니다.

 

폭탄터지기의 결과값

💛 글을 마무리하며.

 

처음으로 작성하는 알고리즘의 유형이라 부족한점이 많다고 생각합니다. 하지만 글을 작성하면서 같은 시뮬레이션이라도 폭탄이 터지는 시뮬레이션 문제중 폭탄이 터지는 유형, 인덱스를 밑으로 내리는 유형또한 익히게 됐던것 같습니다. 앞으로 좀 더 노력해서 시뮬레이션을 필두로 DP, DFS ,BFS 등 많은 유형들을 사람들과 함께 지식을 나누며 저에게 문제 해결력을 키우는 개발자가 되겠습니다.