수천 년 동안 잊혀진 고대 문명의 유적을 발견하게 되었습니다. 이 유적지는 격자 형태로 되어 있으며, 각 칸에는 다양한 유물의 조각이 배치되어 있습니다. 유물 조각은 총 가지 종류로, 각각 숫자 부터 로 표현됩니다.
[1] 탐사 진행
격자 선택
당신은 고고학자로서 격자 내에서 격자를 선택하여 격자를 회전시킬 수 있습니다. 선택된 격자는 시계 방향으로 90도, 180도, 270도 중 하나의 각도만큼 회전시킬 수 있습니다. 단, 선택된 격자는 항상 회전을 진행해야만 합니다.
예를 들어, 다음과 같이 유적지가 존재한다고 가정해보겠습니다.
만약 회전 중심 좌표를 으로 설정하고, 90도 회전하면 유적지는 다음과 같이 바뀌게 됩니다.
회전 목표
가능한 회전의 방법 중 (1) 유물 1차 획득 가치를 최대화하고, 그러한 방법이 여러가지인 경우 (2) 회전한 각도가 가장 작은 방법을 선택합니다. 그러한 경우도 여러가지인 경우 (3) 회전 중심 좌표의 열이 가장 작은 구간을, 그리고 열이 같다면 행이 가장 작은 구간을 선택합니다.
[2] 유물 획득
유물 1차 획득
상하좌우로 인접한 같은 종류의 유물 조각은 서로 연결되어 있습니다. 이 조각들이 개 이상 연결된 경우, 조각이 모여 유물이 되고 사라집니다. 유물의 가치는 모인 조각의 개수와 같습니다.
예를 들어, 아래와 같이 유적지가 존재한다면 유물은 총 7개의 조각으로 이루어지게 됩니다.
각각 개, 개의 조각이 모이므로 얻게 되는 유물의 가치는 총 이 됩니다.
이 유적지에서 유물이 사라지고 난 이후의 모습은 다음과 같습니다.
유적의 벽면에는 부터 사이의 숫자가 개 적혀 있습니다. 이들은 유적에서 조각이 사라졌을 때 새로 생겨나는 조각에 대한 정보를 담고 있습니다.
예를 들어, 유적의 벽면에 아래와 같이 새로 생겨나는 조각에 대한 정보는 아래와 같습니다.
조각이 사라진 위치에는 유적의 벽면에 적혀있는 순서대로 새로운 조각이 생겨납니다. 새로운 조각은 (1) 열 번호가 작은 순으로 조각이 생겨납니다. 만약 열 번호가 같다면 (2) 행 번호가 큰 순으로 조각이 생겨납니다. 단, 벽면의 숫자는 충분히 많이 적혀 있어 생겨날 조각의 수가 부족한 경우는 없다고 가정해도 좋습니다.
위의 예시에서 새로운 조각들이 채워지는 방법에 따른 순서를 나타내면 다음과 같습니다.
따라서 조각은 아래와 같이 채워집니다.
단, 유적의 벽면에 써 있는 숫자를 사용한 이후에는 다시 사용할 수 없으므로 이후 부터는 남은 숫자부터 순서대로 사용합니다. 즉, 이후에는 아래 그림에서 8번째로 적혀있는 수인 1부터 다시 사용이 가능합니다.
유물 연쇄 획득
새로운 유물 조각이 생겨난 이후에도 조각들이 3개 이상 연결될 수 있습니다. 이 경우 앞과 같은 방식으로 조각이 모여 유물이 되고 사라집니다. 사라진 위치에는 또다시 새로운 조각이 생겨나며 이는 더 이상 조각이 3개 이상 연결되지 않아 유물이 될 수 없을 때까지 반복됩니다.
위의 예시에서는 새로운 유물 조각이 생겨난 이후에도 다음과 같이 유물이 만들어집니다. 따라서 연쇄적으로 유물을 획득하는 과정을 반복해야 합니다.
[3] 탐사 반복
이 문제에서는 탐사 진행 ~ 유물 연쇄 획득의 과정까지를 1턴으로 생각하며, 총 번의 턴에 걸쳐 진행됩니다.
각 턴마다 획득한 유물의 가치의 총합을 출력하는 프로그램을 작성해야 합니다. 단, 아직 번의 턴을 진행하지 못했지만, 탐사 진행 과정에서 어떠한 방법을 사용하더라도 유물을 획득할 수 없었다면 모든 탐사는 그 즉시 종료됩니다. 이 경우 얻을 수 있는 유물이 존재하지 않음으로, 종료되는 턴에 아무 값도 출력하지 않음에 유의합니다.
입력 형식
첫 번째 줄에 탐사의 반복 횟수 와 벽면에 적힌 유물 조각의 개수 이 공백을 사이에 두고 주어집니다.
그 다음 개의 줄에 걸쳐 유물의 각 행에 있는 유물 조각에 적혀 있는 숫자들이 공백을 사이에 두고 순서대로 주어집니다.
그 다음 줄에는 벽면에 적힌 개의 유물 조각 번호가 공백을 사이에 두고 순서대로 주어집니다.
단, 초기에 주어지는 유적지에서는 탐사 진행 이전에 유물이 발견되지 않으며, 첫 번째 턴에서 탐사를 진행한 이후에는 항상 유물이 발견됨을 가정해도 좋습니다.
- 유물 조각 번호
출력 형식
첫 번째 줄에 각 턴 마다 획득한 유물의 가치의 총합을 공백을 사이에 두고 출력합니다.
입출력 예제
예제1
입력:
2 20
7 6 7 6 7
6 7 6 7 6
6 7 1 5 4
7 6 3 2 1
5 4 3 2 7
3 2 3 5 2 4 6 1 3 2 5 6 2 1 5 6 7 1 2 3
출력:
17
예제2
입력:
2 30
7 6 7 6 7
6 7 6 7 6
6 7 1 5 4
7 6 3 2 1
5 4 3 2 7
3 2 3 5 2 4 6 1 3 2 5 6 2 1 6 6 7 5 4 2 2 3 1 3 1 2 4 2 1 3
출력:
17 3
생각한 점
1. 새로운 조각은 (1) 열 번호가 작은 순으로 조각이 생겨납니다. 만약 열 번호가 같다면 (2) 행 번호가 큰 순으로 조각이 생겨납니다.
이처럼 ~순으로 조각 생성의 경우 탐색의 순서라고 봐도 무방하다.
필자는 처음에 클래스를 만들어서 정렬해야 한다고 생각했는데, 어렵게 생각하지 말고 반복문의 탐색 순서로 적용하면 되겠다.
예시를 들자면 이렇다.
for (int i = 최소 열 번호; i <= 최대 열 번호; i++) {
for (int j = 최대 행 번호; j <= 최소 행 번호; j++) {
// 수행
}
}
2. 유적의 벽면에 써있는 숫자를 처음에는 배열에 저장해서 인덱스를 따로 관리했는데, 나중에 정답 코드를 확인하니 Queue로 구현하는 것이 훨씬 편해보여서 코드를 수정했다.
3. 3x3배열을 시계방향으로 회전시킬 때의 인덱스를 주의하자 .. 이 부분에서 헷갈려서 삽질을 많이 했다.
N * N 배열에서 (i, j)을 90도 회전시키면 -> 해당 값이 (j, len-i-1)로 옮겨진다.
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
tmpArr[j][arr.length-1-i] = arr[i][j];
}
}
4. 탐사가 중지될 경우의 조건을 잘 확인해야 한다 !!
정답 코드
import java.util.*;
import java.io.*;
public class Main {
static int k, m;
static int[][] map = new int[5][5]; // 기본 맵
static Queue<Integer> pieces = new LinkedList<>(); // 새로운 유물 조각
static boolean[][] visited = new boolean[5][5];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int k = Integer.parseInt(st.nextToken()); // 탐사 반복 횟수
int m = Integer.parseInt(st.nextToken()); // 유물 조각 개수
for (int i = 0; i < 5; i++) { // map 저장
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) { // 새로운 유물 조각 저장
int tmp = Integer.parseInt(st.nextToken());
pieces.offer(tmp);
}
int ans = 0;
for (int i = 0; i < k; i++) { // k번 탐사
int val = 0;
int xx = 0; // 이번 턴 최종 x좌표
int yy = 0; // 이번 턴 최종 y좌표
int angle = 0; // 이번 턴 최종 각도
boolean flag = false; // 유물이 더 나오는지 확인
// 1. 회전(총 9번 * 3각도)
for (int a = 0; a < 3; a++) { // 각도가 가장 작은 방법 (0:90, 1: 180, 2: 270)
for (int y = 1; y <= 3; y++) { // 열이 가장 작은 구간
for (int x = 1; x <= 3; x++) { // 중심 좌표 기준(행이 가장 작은 구간)
int[][] nowMap = makeMap(x, y, a); // 현재 맵
visited = new boolean[5][5];
// 2. 유물 획득
int tmp = 0;
for (int j = 0; j < 5; j++) {
for (int p = 0; p < 5; p++) {
if (!visited[j][p]) {
tmp += bfs(j, p, nowMap);
}
}
}
// 3. 가치 계산
if (val < tmp) { // 가치 업데이트
val = tmp;
xx = x;
yy = y;
angle = a;
}
}
}
}
// 4. 실제로 회전하고 맵 업데이트
if (xx == 0 && yy == 0) break;
map = makeMap(xx, yy, angle);
val = 0;
while (true) {
int tmp = 0;
visited = new boolean[5][5];
for (int j = 0; j < 5; j++) {
for (int p = 0; p < 5; p++) {
if (!visited[j][p]) {
tmp += bfs(j, p, map);
}
}
}
if (tmp <= 0) break;
val += tmp;
refreshMap(); // 맵 채우기
}
sb.append(val).append(" ");
}
System.out.println(sb);
}
static int[][] copyMap(int[][] target) { // 맵 복사
int[][] tmp = new int[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
tmp[i][j] = target[i][j];
}
}
return tmp;
}
static int[][] makeMap(int x, int y, int angle) { // 각도 별 회전한 맵 만들기
int[][] tmp = copyMap(map);
switch(angle) {
case 0: // 90도
tmp = rotation(x, y, tmp);
break;
case 1: // 180도
for (int i = 0; i < 2; i++) {
tmp = rotation(x, y, tmp);
}
break;
case 2: // 270도
for (int i = 0; i < 3; i++) {
tmp = rotation(x, y, tmp);
}
break;
}
return tmp;
}
static int[][] rotation(int x, int y, int[][] arr) { // 회전한 배열 만들기
int[][] tmp3 = new int[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
tmp3[j][2-i] = arr[i+x-1][j+y-1];
}
}
int[][] tmp5 = copyMap(arr);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
tmp5[x + i - 1][y + j - 1] = tmp3[i][j];
}
}
return tmp5;
}
static int bfs(int x, int y, int[][] nowMap) { // 연결된 유물 조각 개수 (3개 이상일 때 cnt리턴, 3개 미만일 경우 0 리턴)
int[][] dirs = {{1,0}, {0,1}, {-1, 0}, {0, -1}}; // 상하좌우 방향
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true;
int cnt = 1; // 유물 조각 개수
List<int[]> list = new ArrayList<>(); // 사라질 유물 위치
while (!queue.isEmpty()) {
int[] cur = queue.poll();
list.add(new int[]{cur[0], cur[1]});
for (int[] dir : dirs) {
int dx = cur[0] + dir[0];
int dy = cur[1] + dir[1];
if (dx >= 0 && dx < 5 && dy >= 0 && dy < 5) {
if (!visited[dx][dy] && (nowMap[dx][dy] == nowMap[cur[0]][cur[1]])) { // 방문하지 않았고 같은 종류면
cnt += 1;
list.add(new int[]{dx, dy});
queue.offer(new int[]{dx, dy});
visited[dx][dy] = true;
}
}
}
}
if (cnt >= 3) { // 연결된 유물이 3개 이상일 경우
for (int[] cur : list) {
nowMap[cur[0]][cur[1]] = 0;
}
return cnt;
}
return 0;
}
static void refreshMap() { // 사용된 유물인 경우 유물을 채워넣음
for (int x = 0; x < 5; x++) {
for (int y = 4; y >= 0; y--) {
if (map[y][x] == 0 && !pieces.isEmpty()) {
map[y][x] = pieces.poll();
}
}
}
}
static void printMap(int[][] map) {
for (int b = 0; b < map.length; b++) {
System.out.println();
for (int c = 0; c < map[0].length; c++) {
System.out.print(map[b][c] + " ");
}
}
System.out.println();
}
}'알고리즘' 카테고리의 다른 글
| [코드트리] 루돌프의 반란 (JAVA) (2) | 2024.12.05 |
|---|