문제 설명
25331번: Drop 7
Drop7은 7×7 크기의 격자에서 진행하는 싱글 플레이어 게임이다. 처음에는 격자가 비어있고, 플레이어는 매 턴마다 1 이상 7 이하의 정수 하나가 적힌 공을 받아 7개의 열 중 한 곳에 떨어뜨려야 한
www.acmicpc.net
접근 방법
해당 문제는 원티드 주관 코딩테스트 대회 2022년 2회차 문제로서 당시 시간적 여유가 있었음에도 불구하고 문제 해결을 위한 아이디어가 떠오르지 않아 제대로 접근조차 하지 못했었던 문제였습니다. 그래서 아쉬운 마음에 코딩테스트 이후에 따로 시간을 내서 재도전 해보았습니다. 우선 문제를 해결하기 위해 접근했었던 방법을 단계별로 나타내면 다음과 같습니다.
1. 각 열별로 공 떨어트리기
- 떨어뜨린 공은 이미 배치되어 있는 공 바로 위에 도달하거나 바닥 바로 위에 도달할 때까지 아래로 이동해야함
2. (1번에서 공을 떨어트린 후) 7 * 7 격자 내에서 터질 수 있는(없어질 수 있는) 공의 좌표 리스트 구하기
3. 2번에서 구한 공의 좌표들을 토대로 공을 터트리기
- 터트린 후에는 터트린 지점 위에 있는 공들이 모두 한칸씩 내려와야 함
4. 터트릴 수 있는 공이 없을 때까지 앞선 2 ~ 3번 작업을 반복
5. 격자 내에 존재하는 공의 개수 카운팅
- 결과값을 최소값으로 초기화
6. 현재 격자를 최초의 격자로 초기화
개인적으로는 이 문제를 일종의 빡구현(?) 방식으로 해결해볼 수 있었는데, 각 단계별로 자세히 살펴보겠습니다.
각 열별로 공 떨어트리기
문제에서 주어진 격자는 7 * 7의 격자이므로 공은 각 열에(인덱스 기준 0 ~ 6) 공을 떨어트려 총 7가지의 경우의 수를 고려하면 되겠습니다.
입력으로 주어지는 번호의 공을 for문을 통해 7개의 각 열에 대해 떨어트리도록 했습니다. 이때 각 열의 가장 위에 있는 공 바로 위에 떨어져야 하며, 공이 없는 경우에는 바닥 바로 위에 떨어지도록 해야합니다.
즉, 각 열의 최하단부터 탐색하면서 0이 가장 먼저 나오는 곳에 해당 공을 위치시키면 됩니다. 이를 로직으로 나타내면 다음과 같습니다.
// ...
int ball = Integer.parseInt(br.readLine());
for (int col = 0; col < 7; col++) {
fall(ball, col);
// ...
}
}
private static void fall(int ball, int column) {
for (int i = 6; i > -1; i--) {
if (board[i][column] == 0) {
board[i][column] = ball;
break;
}
}
}
터질 수 있는 공의 좌표 리스트 구하기
이제 공을 떨어트렸으니 터질 수 있는 공의 좌표 리스트를 구해야합니다. 현재의 7 * 7 격자 상 0이 아닌 좌표(공이 있는 좌표)를 순회하면서 해당 좌표에서 가로 및 세로 그룹(연속적으로 배치되어 있는 공의 그룹) 상에 있는 공들이 터질 수 있는지를 검사하도록 했습니다.
우선 해당 좌표의 가로 및 세로 그룹, 각 그룹별 개수가 몇 개인지를 카운팅했고 이후에 각 그룹 내 카운팅한 숫자의 공이 있는지 검사합니다. 이때 해당되면 HashSet 자료구조에 해당 좌표 정보를 List에 담아 저장하도록 했는데, 이는 동일한 좌표가 여러 개 추가되지 않도록 하기 위함입니다.
private static Set<List<Integer>> findBurstPositions() {
Set<List<Integer>> burstPositions = new HashSet<>();
for (int row = 0; row < 7; row++) {
for (int col = 0; col < 7; col++) {
if (board[row][col] != 0) {
int heightCount = countHeight(row, col), widthCount = countWidth(row, col);
/* countHeight와 countWidth 메서드 구현 내용은 아래 전체 소스 코드를 참고해주세요 */
// 세로 그룹 상 heightCount에 해당하는 공의 좌표 Set에 추가
for (int i = row; i < 7; i++) {
if (board[i][col] == heightCount) {
burstPositions.add(Arrays.asList(i, col));
} else if (board[i][col] == 0) {
break;
}
}
for (int i = row - 1; i > -1; i--) {
if (board[i][col] == heightCount) {
burstPositions.add(Arrays.asList(i, col));
} else if (board[i][col] == 0) {
break;
}
}
// 가로 그룹 상 widthCount에 해당하는 공의 좌표 Set에 추가
// ... (생략) ...
}
}
}
// ...
}
공 터트리기
이제 앞서 구한 터질 수 있는 공의 좌표 리스트를 통해 공을 터트리는 작업을 합니다. 공을 터트린다는 것은 해당 좌표의 값을 0으로 초기화한다는 것인데, 이때 중요한 것은 해당 좌표 위에 어떤 공들이 존재하는 경우 해당 공들이 모두 한 칸씩 내려와야한다는 점입니다.
우선적으로 터지는 공들의 좌표 값들을 모두 0으로 할당해줍니다. 이후 해당 좌표가 존재하는 열에 있는 공들 사이사이에 빈틈(0의 값)이 존재하는 경우 이들을 하단부터 차근차근 쌓아올려 놓도록 했습니다. 이때 저 같은 경우에는 터지는 공들의 좌표의 열 값을 Set 자료구조에 저장하고(중복되지 않도록), 각 열에 존재하는 공(0의 값은 제외)들을 List 자료구조에 추가시켜 해당 값들을 최하단에서부터 쌓아올리도록 했습니다.
// ...
columns = new HashSet<>();
for (List<Integer> burstPosition : burstPositions) {
board[burstPosition.get(0)][burstPosition.get(1)] = 0;
columns.add(burstPosition.get(1));
}
for (Integer column : columns) {
fallAfterBurst(column);
}
}
// ...
}
}
private static void fallAfterBurst(int column) {
List<Integer> numbers = new ArrayList<>();
for (int i = 6; i > -1; i--) {
if (board[i][column] != 0) {
numbers.add(board[i][column]);
board[i][column] = 0;
}
}
int i = 6;
for (Integer number : numbers) {
board[i--][column] = number;
}
}
터트릴 수 있는 공이 없을 때까지 앞선 작업 반복
공을 다 터트린 이후에는 연쇄적으로 다른 공들이 터지는 이벤트가 발생할 수 있기 때문에 추가적으로 터질 수 있는 공의 좌표가 없을 때까지 앞서 터질 수 있는 공의 좌표들을 구하는 작업과 공을 터트리는 작업을 반복해주도록 합니다.
// ...
Set<List<Integer>> burstPositions;
Set<Integer> columns;
while ((burstPositions = findBurstPositions()) != null) {
columns = new HashSet<>();
for (List<Integer> burstPosition : burstPositions) {
board[burstPosition.get(0)][burstPosition.get(1)] = 0;
columns.add(burstPosition.get(1));
}
for (Integer column : columns) {
fallAfterBurst(column);
}
}
// ...
격자 내에 존재하는 공의 개수 카운팅
이제 더이상 터질 공들이 없으므로 현재 격자상에 존재하는 공의 개수를 세어줍니다. 이후에는 결과 값을 최소값으로 갱신해줍니다.
// ...
result = Math.min(result, count());
// ...
}
private static int count() {
int count = 0;
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if (board[i][j] != 0) {
count++;
}
}
}
return count;
}
현재 격자를 최초의 격자로 초기화
이제 첫 번째 열에 공을 떨어트렸을 경우 격자 상에 남게 되는 공의 개수를 고려해주었으니, 다음 열에 대해 앞선 작업들을 반복해주면 되겠습니다. 이를 위해 처음 좌표 값을 입력받을 때 원본 데이터를 별도로 저장해주었으며, 앞선 작업들을 끝마친 후에 원본 데이터를 통해 기존 격자 데이터를 초기화해주도록 합니다.
// ...
init();
}
private static void init() {
for (int i = 0; i < 7; i++) {
System.arraycopy(origin[i], 0, board[i], 0, 7);
}
}
종합적인 소스 코드는 아래 항목을 참고해주세요. 참고적으로 현재의 제 로직 상에는 중복되는 작업들이 존재하기 때문에 성능적으로 완벽하다고 보기 힘들어 성능 개선을 위한 리팩토링 작업은 별도로 필요하겠습니다. 😅 (추후 리팩토링 시에 업데이트할 예정)
전체 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
class Main {
static int[][] board = new int[7][7], origin = new int[7][7];
static int result = 49;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < 7; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 7; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
origin[i][j] = board[i][j];
}
}
int ball = Integer.parseInt(br.readLine());
for (int col = 0; col < 7; col++) {
fall(ball, col);
Set<List<Integer>> burstPositions;
Set<Integer> columns;
while ((burstPositions = findBurstPositions()) != null) {
columns = new HashSet<>();
for (List<Integer> burstPosition : burstPositions) {
board[burstPosition.get(0)][burstPosition.get(1)] = 0;
columns.add(burstPosition.get(1));
}
for (Integer column : columns) {
fallAfterBurst(column);
}
}
result = Math.min(result, count());
if (result == 0) {
break;
}
init();
}
System.out.println(result);
}
private static void fall(int ball, int column) {
for (int i = 6; i > -1; i--) {
if (board[i][column] == 0) {
board[i][column] = ball;
break;
}
}
}
private static Set<List<Integer>> findBurstPositions() {
Set<List<Integer>> burstPositions = new HashSet<>();
for (int row = 0; row < 7; row++) {
for (int col = 0; col < 7; col++) {
if (board[row][col] != 0) {
int heightCount = countHeight(row, col), widthCount = countWidth(row, col);
for (int i = row; i < 7; i++) {
if (board[i][col] == heightCount) {
burstPositions.add(Arrays.asList(i, col));
} else if (board[i][col] == 0) {
break;
}
}
for (int i = row - 1; i > -1; i--) {
if (board[i][col] == heightCount) {
burstPositions.add(Arrays.asList(i, col));
} else if (board[i][col] == 0) {
break;
}
}
for (int i = col; i < 7; i++) {
if (board[row][i] == widthCount) {
burstPositions.add(Arrays.asList(row, i));
} else if (board[row][i] == 0) {
break;
}
}
for (int i = col - 1; i > -1; i--) {
if (board[row][i] == widthCount) {
burstPositions.add(Arrays.asList(row, i));
} else if (board[row][i] == 0) {
break;
}
}
}
}
}
if (burstPositions.size() == 0) {
return null;
}
return burstPositions;
}
private static int countHeight(int row, int col) {
int heightCount = 0;
for (int i = row; i < 7; i++) {
if (board[i][col] != 0) {
heightCount++;
} else {
break;
}
}
for (int i = row - 1; i > -1; i--) {
if (board[i][col] != 0) {
heightCount++;
} else {
break;
}
}
return heightCount;
}
private static int countWidth(int row, int col) {
int widthCount = 0;
for (int i = col; i < 7; i++) {
if (board[row][i] != 0) {
widthCount++;
} else {
break;
}
}
for (int i = col - 1; i > -1; i--) {
if (board[row][i] != 0) {
widthCount++;
} else {
break;
}
}
return widthCount;
}
private static void fallAfterBurst(int column) {
List<Integer> numbers = new ArrayList<>();
for (int i = 6; i > -1; i--) {
if (board[i][column] != 0) {
numbers.add(board[i][column]);
board[i][column] = 0;
}
}
int i = 6;
for (Integer number : numbers) {
board[i--][column] = number;
}
}
private static int count() {
int count = 0;
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if (board[i][j] != 0) {
count++;
}
}
}
return count;
}
private static void init() {
for (int i = 0; i < 7; i++) {
System.arraycopy(origin[i], 0, board[i], 0, 7);
}
}
}
예제 외 반례
0 0 0 0 0 0 0
7 5 5 5 5 5 0
5 5 5 5 5 5 6
4 4 4 4 4 4 4
4 4 4 4 4 4 4
2 2 2 2 2 2 2
2 2 2 2 2 2 2
6
정답 : 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 2 0 0 0 0 0
0 2 0 0 0 0 0
2 4 4 4 4 0 0
2
정답 : 0
참고 자료
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 - 1068] 트리 - Java (0) | 2022.08.17 |
|---|---|
| [백준 - 25332] 수들의 합 8 - Java (0) | 2022.08.11 |
| [백준 - 14503] 로봇 청소기 - Java (0) | 2022.08.03 |
| [백준 - 1806] 부분합 - Java (0) | 2022.08.03 |
| [백준 - 11725] 트리의 부모 찾기 - Java (0) | 2022.08.02 |