SW Academy 5656 벽돌 깨기 JAVA

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&problemTitle=%EB%B2%BD%EB%8F%8C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

https://github.com/JUNGSOONIL/JAVA/blob/main/SW%EF%BB%BFAcademy%205656

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 map가 주어지고 공을 위에서부터 떨어트려 벽돌을 깰 때

벽돌이 남는 최소 개수를 구하는 문제다.

​

근데 특이한 점은 공이 떨어져서 해당 벽돌에 부딪히면 해당 벽돌의 값 -1 만큼 상하좌우 벽돌도

부서지며 이때 부서지는 벽돌들도 똑같이 상하좌우를 터트린다.

​

이후 빈칸에 대해서는 아래로 한 칸 내려오게 되고 공의 개수만큼 반복하는 문제다.

​

해당 문제는 중복 순열과 bfs를 이용해서 해결했으며, 아래로 내리는 부분에서는 stack도 이용했다.

​

1. 처음에 입력 처리를 해준 뒤 중복순열을 만들어 준다.

2. 중복순열로 만들어진 값을 out 배열에 넣어준 뒤 먼저 map를 copy 해 준다.

(카피한 배열에 연산을 실시하고 다시 원래 값을 가져오기 위해)

3. 공을 움직인다 out 배열에 있는 값을 가지고 열을 비교하면서 벽돌이 있으면 해당 값을 bfs에 넣어준다.

4. 3번에서 들어온 값을 가지고 상하좌우 범위만큼 체크를 하며 탐색한다 이때 이동거리는 처음 값 -1

5. bfs를 통해 체크하여 벽돌을 모두 깨고 나면 빈칸에 대해서 아래로 당겨준다.

(반복문을 통해 열 별러 값을 스택에 넣고 젤 아래부터 하나씩 pop 해서 넣어줌)

6. 현제 결과 배열을 탐색하면서 벽돌의 칸을 하나씩 체크한 뒤, ans에 최솟값을 갱신해 준다.

​