문제
입력
첫 번째 줄에 탐사의 반복 횟수 K와 벽면에 적힌 유물 조각의 개수 M이 공백을 사이에 두고 주어집니다.
그 다음 5개의 줄에 걸쳐 유물의 각 행에 있는 유물 조각에 적혀 있는 숫자들이 공백을 사이에 두고 순서대로 주어집니다.
그 다음 줄에는 벽면에 적힌 M개의 유물 조각 번호가 공백을 사이에 두고 순서대로 주어집니다.
출력
첫 번째 줄에 각 턴 마다 획득한 유물의 가치의 총합을 공백을 사이에 두고 출력합니다
풀이
제한조건
- 1≤K≤10
- 10≤M≤300
- 1≤ 유물 조각 번호 ≤7
접근방법
시뮬레이션
문제를 충분히 꼼꼼하게 읽었는지 고민해보자.
스스로 잘 읽었는지 의심스럽다면 한 번 더 읽자.
문제를 읽었다면 어떤것을 구현해야하는지 확인해보자.
- 배열 돌리기 ( 90, 180, 270)
- 탐색
- 블록 부수기
- 블록 채우기그럼 시뮬레이션 순서를 정리해보자.
1. 탐사 진행.
2. 유물 획득
3. 채우기.
4. 보너스 점수
5. 턴 종료여기서 문제를 똑바로 읽어야하는 이유가 나온다.
1. 탐사 진행을 위한 우선 순위.
2. 채우기 시 우선 순위.
3. 보너스 점수의 획득 조건.
4. 부가적인 턴 종료 조건.배열을 회전시키는 부분에서 실수하지 않도록 주의하자.
알고리즘적 스킬을 많이 요구하지 않는 문제이다.
차근차근 구현하면 된다.
아래 코드는 통과하는 코드이지만.. 매우 이해하기 어려우므로 아이디어만 몇가지 기록해두자면
-
전체 맵의 크기가 크지 않다.
전체 맵이 5x5크기이고, 회전하는 배열은 3x3이다. 또한 아무리 시뮬레이션을 돌려도 턴이 최대 10턴 밖에 없다. 부담을 가지지 말고 접근하자. -
채우기에 사용하는 유물 조각은 큐로 관리
문제가 제법 복잡하기에 배열로 관리한다면, 나중에 인덱스가 섞일 수 있다.(혼동 우려)
큐에서 꺼내쓰고 머리에서 지우자.
또한 1번 처럼 크기가 크지 않으므로 전체를 순회하며 지운부분을 채워나가자. -
3칸 이상 인접하여 파괴할 수 있는 지점 좌표 기록해두기.
처음 탐사진행 과정에서 어디서 찾을 수 있는 정보를 활용해보자.
어디서 탐색해야 3칸 이상 인접한 블럭이 나오는지 탐사진행과정에서 찾는다.
이를 List에 저장해두면, 유물을 획득하는 과정에서 해당 위치부터만 탐색하면 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int K, M, maxRoundScore;
static StringBuilder sb = new StringBuilder();
static List<Integer> scoreList;
static Queue<Integer> spare;
static boolean[][] visit;
static int[][] arr;
static List<int[]> list, temp;
final static int SIZE = 5;
public static void main(String[] args) throws Exception {
// input
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = in.readLine().split(" ");
K = stoi(inputs[0]);
M = stoi(inputs[1]);
arr = new int[SIZE][SIZE];
spare = new ArrayDeque<>();
for (int i = 0; i < SIZE; ++i) {
inputs = in.readLine().split(" ");
for (int j = 0; j < SIZE; ++j) {
arr[i][j] = stoi(inputs[j]);
}
}
inputs = in.readLine().split(" ");
for (int i = 0; i < M; ++i)
spare.add(stoi(inputs[i]));
simulation();
for (int value : scoreList)
sb.append(value + " ");
sb.append("\n");
System.out.println(sb);
}
private static void simulation() {
scoreList = new ArrayList<>();
for (int t = 0; t < K; ++t) {
maxRoundScore = 0;
list = new ArrayList<>();
temp = new ArrayList<>();
// 가장 점수를 많이 획득할 수 있는 지점을 구하자
int[] expect = getExpectPosition();
// 점수를 획득할 수 없던 경우 바로 종료
if (list.size() == 0)
return;
// rotate(x,y,degree) 특정 좌표를 기준으로 구한 각도로 회전
arr = rotate(expect[0], expect[1], expect[2]);
// 지우기
for (int[] pos : list)
removeItem(pos[0], pos[1]);
// 채우기
fillItem();
// 추가 점수 획득
while (true) {
visit = new boolean[SIZE][SIZE];
int count = 0;
temp.clear();
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
count += bfs(i, j, arr);
}
}
if (count == 0)
break;
visit = new boolean[SIZE][SIZE];
for (int[] pos : temp)
removeItem(pos[0], pos[1]);
fillItem();
maxRoundScore += count;
}
scoreList.add(maxRoundScore);
}
}
private static void removeItem(int x, int y) {
visit = new boolean[SIZE][SIZE];
visit[x][y] = true;
int base = arr[x][y];
arr[x][y] = 0;
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {x, y});
while (!q.isEmpty()) {
int[] pos = q.poll();
for (int d = 0; d < 4; ++d) {
int nx = pos[0] + dx[d];
int ny = pos[1] + dy[d];
if (!isInRange(nx, ny))
continue;
if (!visit[nx][ny] && arr[nx][ny] == base) {
visit[nx][ny] = true;
arr[nx][ny] = 0;
q.add(new int[] {nx, ny});
}
}
}
}
private static void fillItem() {
for (int j = 0; j < SIZE; ++j) {
for (int i = 4; i >= 0; --i)
if (arr[i][j] == 0)
arr[i][j] = spare.poll();
}
}
private static int[] getExpectPosition() {
int max = 0;
int rx = -1;
int ry = -1;
int rd = -1;
// 우선순위를 고려하여 위치 찾기.
for (int d = 1; d < 4; ++d) {
for (int j = 1; j < 4; ++j) {
for (int i = 1; i < 4; ++i) {
int[][] rotateArr = rotate(i, j, d);
visit = new boolean[SIZE][SIZE];
temp.clear();
int score = 0;
for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 3; ++c) {
if (!visit[r + i - 1][c + j - 1])
score += bfs(r + i - 1, c + j - 1, rotateArr);
}
}
if (score > max) {
list.clear();
list.addAll(temp);
rx = i;
ry = j;
rd = d;
max = score;
}
}
}
}
maxRoundScore += max;
return new int[] {rx, ry, rd};
}
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
private static int bfs(int x, int y, int[][] rotateArr) {
int count = 1;
visit[x][y] = true;
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {x, y});
while (!q.isEmpty()) {
int[] pos = q.poll();
for (int d = 0; d < 4; ++d) {
int nx = pos[0] + dx[d];
int ny = pos[1] + dy[d];
if (!isInRange(nx, ny))
continue;
if (!visit[nx][ny] && rotateArr[nx][ny] == rotateArr[x][y]) {
count++;
visit[nx][ny] = true;
q.add(new int[] {nx, ny});
}
}
}
if (count > 2) {
temp.add(new int[] {x, y});
return count;
}
return 0;
}
public static int[][] rotate(int x, int y, int d) {
int[][] copy = new int[3][3];
int[][] rotateArr = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j)
rotateArr[i][j] = arr[i][j];
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j)
if (d == 1) // 90도 회전
copy[i][j] = arr[3 - j + x - 2][i + y - 1];
else if (d == 2) // 180도 회전
copy[i][j] = arr[3 - i + x - 2][3 - j + y - 2];
else // 270도 회전
copy[i][j] = arr[j + x - 1][3 - i + y - 2];
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j)
rotateArr[i + x - 1][j + y - 1] = copy[i][j];
}
return rotateArr;
}
public static boolean isInRange(int x, int y) {
if (0 <= x && x < SIZE && 0 <= y && y < SIZE)
return true;
return false;
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}