아 맞다, 그거
코드 트리에서 삼성 코테 기출 문제인 "고대 문명 유적 탐사" 문제에 대한 풀이입니다.
코드트리 - 고대 문명 유적 탐사
원리
- 좀 우려되는 부분이 있는데, 이런 구현 문제는 코드를 가지고 설명하는 것이 정말 힘들다.
- 따라서 아이디어를 잘 공유하기 위해 애써야 하는데 워낙 조건이 많다보니 내가 누군가를 이해시킬 수 있을만큼 친절하게 쓸 수 있는지 모르겠다.
- 또, 코드 트리에는 해설이 포함되어 있기 때문에 크게 의미가 없을 수도 있다.
1. 유적지 회전
- 이 문제는 내가 처음으로 풀었던 삼성 기출 문제였다.
- 물론 백준에서도 몇 가지를 풀었었는데, 항상 main() 함수에 모든 풀이를 다 넣었기 때문에 디버깅이 무척 어려웠다.
- 나는 멋도 모르고 이 문제 역시 비슷하게 하나의 함수에서 해결하려고 노력했다.
- 따라서 가독성이 너무 안좋다.
- maps는 기본적으로 유적지 정보를 갖는다.
- 그리고 turnSetta() 함수에서는 이 maps를 회전한다.
- 즉, maps 자체가 변한다.
- 쉽게 구현하려면 원본 maps를 변경하는 것이 아니라 변경된 배열을 반환하도록 하는 것이 좋았다고 생각한다.
- 3x3 회전이기 때문에 turnSetta() 함수는 비교적 간단하다.
- 물론, 좌표 값을 직접 컨트롤해도 되지만 조금이라도 코드 량을 줄이고자 for문을 이용해서 풀었다.
- (0, 0) 시작 (r-1, c-1)가 끝일 때, (1, 1)부터 (r-2, c-2)를 중심점으로 회전할 수 있으므로 각 좌표를 중심으로 일일히 회전하고 유물을 얼마나 획득할 수 있을지 계산했다.
- 가장 큰 유물을 획득할 때의 maps 형태를 newMaps에 저장해둔다.
- 유물 획득량은 2번에서 설명한다.
2. 유물 획득
- 유물 획득 과정은 간단하다.
- (0, 0)부터 (r-1, c-1)까지 각 좌표에서 dfs()를 돌린다.
- 이 함수는 calcMystery()이다.
- 근데 문제는 이 dfs()함수인데 이게 좀 복잡하다.
- 현재 칸에서 내가 다음에 방문할 수 있는 칸들에서 얻을 수 있는 유물 값을 반환받는다.
- 그리고 현재 칸 역시 1개의 유물이므로 현재 칸의 유물 값도 더한다.
- 이 값은 ret에 저장되며, dfs 함수의 반환 값과도 같다.
- (이걸 어떻게 생각했지...? 내 스스로가 좀 기특하다...)
- 특정 칸에서 dfs가 진행되고 방문된 칸들은 tempVisited 배열에 1로 체크가 된다.
- 근데 만약 유물 칸 수가 3개 미만이면 획득한 것으로 처리하면 안된다.
- 이것은 현재 유물 값이 5일 때, 15 미만의 유물 값을 획득했다면 3칸을 차마 방문하지 못했다는 것을 간접적으로 알 수 있다.
- 만약 이런 경우라면 tempVisited의 방문 체크된 칸들을 visited 배열에 옮기지 않는다.
- 반대로 3칸 이상의 유물을 획득했다면 tempVisited에 방문 체크된 칸들을 visited 배열로 옮긴다.
- 그리고 value에 현재 유물 획득 수를 더한다.
- 여기서 유물 획득 값은 유적지 배열에 있는 수치들을 그대로 더한 값이고 내가 말한 value에 담긴 값은 몇 칸의 유물을 획득했는지를 의미한다.
- 문제에서는 그냥 칸 수만 세기 때문에 위와 같이 저장했다.
- 유물을 하나도 획득하지 못한다면, 알고리즘이 종료된다.
- 획득한 유물 칸 수는 answer에 더해진다.
3. 유물 획득했으면 해당 칸들을 비우기
- 이것은 visited 배열을 체크하면 어떤 칸들에서 유물을 획득했는지 알 수 있다.
- 그런데 나중에 이 칸들을 채울 때 행과 열을 기준으로 순서가 정해지기 때문에 단순히 비우기만 하는 것이 아니라 해당 칸들의 좌표를 ArrayList에 담아 놓는다.
- 이런 것들도 ArrayList<int[]>로 하는 것보다 추후에 깨달았지만, Point 클래스를 정의한 뒤에 ArrayList<Point>로 정의하는 것이 훨씬 보기가 편하다.
- 그러면 정렬을 어떻게 하냐고?
- JDK의 익명 함수를 이용하면 쉽게 정렬할 수 있다.
- 대충 (o1, o2) -> { return o1 - o2 } 형태가 기본 오름차순 정렬이라면 (o1, o2) -> { return o1.y == o2.y ? o2.x - o1.x : o1.y - o2.y }로 바꿔서 정의하면 된다.
- 이 return은 열 번호가 같으면 행 번호가 큰 순서대로 채우는 것이고, 그렇지 않으면 열 번호가 작은 곳부터 채우는 것을 의미한다.
- 여튼, 이 ArrayList는 아래 코드에서 deletedPoints이다.
- 한 가지 더 작업해주는 것은 유물 획득이 최대일 때의 유적지 지도가 newMaps에 저장되어 있는데, 이제 그 상태에서 변경을 진행할 것이기 때문에 maps로 다시 옮겨준다.
- deletedPoints를 기준에 맞게 정렬한다.
- 갱신될 번호들을 newNumbers라는 큐에 저장해두었기 때문에 poll()을 통해서 값을 하나 가져와서 deletedPoints의 좌표에 순서대로 값들을 옮긴다.
4. 갱신된 상태에서 다시 유물획득 살피기
- 이제 maps를 회전하지 않고, calcMystery() 함수로 몇 개의 유물을 획득할 수 있는지 확인한다.
- 획득한 유물 칸을 비우고 다시 새로운 값들을 채워놓고 다시 유물을 획득할 수 있는지 확인한다.
- 이 과정을 유물을 획득할 수 없을 때까지 반복한다.
- 획득한 유물 칸 수는 answer에 계속 더해진다.
- 만약 유물을 획득할 수 없다면 반복은 종료되고 다음 턴으로 넘어간다.
- 이 과정에서는 2, 3, 4번 과정이 그대로 반복된다.
- 위 함수들을 잘 정의해두면 재사용하면 되기 때문에 어려움이 없다.
- 이렇게 알고리즘이 종료된다.
- 사실 삼성 기출 중에는 가장 쉬운 난이도여서 함수 단위로 잘게 쪼개지 않아도 그나마 쉽게 풀었다.
- 이 문제 같은 경우에 하루 종일이 걸렸던 것 같고, 테스트 케이스에서 틀릴 때 너무 화가나서 진짜 그만둘 뻔 했던 게 수십번이었다...
- 또, Python과 Java를 둘 다 쓰면서 코테를 준비했었던 게 큰 것 같다.
- 그렇지 않았으면 Java 사용에 익숙치 않아서 시간이 더 오래걸렸을 수 있을 것 같다.
- 아, 그리고 삼성 코테를 치러가면 Java의 경우 eclipse만 사용할 수 있기 때문에 집에서도 코테를 연습할 때 eclipse를 사용하는 버릇을 들이자!
- 오랜만에 eclipse를 써서 괜찮나 했는데 다행히도 내가 조교로 Java 실습 수업을 진행할 때 그리고 학부생 때 Java 수업을 들을 때 모두 eclipse를 썼던 사람이라 그렇게 어렵지 않았다.
코드
import java.io.*;
import java.util.*;
public class Main {
int K, M;
int[][] maps;
Queue<Integer> newNumber;
int answer;
int[] dx = new int[] {-1, 0, 1, 0};
int[] dy = new int[] {0, 1, 0, -1};
int[][] visited = new int[5][5];
int[][] tempVisited = new int[5][5];
public void input() throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
K = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maps = new int[5][5];
for (int i = 0; i < 5; i++) {
st = new StringTokenizer(bf.readLine());
for (int j = 0; j < 5; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
}
}
newNumber = new LinkedList<>();
st = new StringTokenizer(bf.readLine());
for (int i = 0; i < M; i++) {
newNumber.add(Integer.parseInt(st.nextToken()));
}
}
public void turnSetta(int[][] m, int x, int y) {
int startX = x - 1;
int startY = y - 1;
for (int j = 0; j < 2; j++) {
int temp = m[startX][startY + j];
m[startX][startY + j] = m[startX + 2 - j][startY];
m[startX + 2 - j][startY] = m[startX + 2][startY + 2 - j];
m[startX + 2][startY + 2 - j] = m[startX + j][startY + 2];
m[startX + j][startY + 2] = temp;
}
}
public int dfs(int depth, int x, int y, int initialNum, int[][] m) {
int ret = m[x][y];
tempVisited[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx > -1 && ny > -1 && nx < 5 && ny < 5) {
if (m[nx][ny] == initialNum && tempVisited[nx][ny] == 0) {
ret += dfs(depth + 1, nx, ny, initialNum, m);
}
}
}
return ret;
}
public int calcMystery(int[][] m) {
int volume = 0;
for (int k = 0; k < 5; k++)
Arrays.fill(visited[k], 0);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (visited[i][j] == 0) {
for (int k = 0; k < 5; k++) {
Arrays.fill(tempVisited[k], 0);
}
int result = dfs(0, i, j, m[i][j], m);
if (result / m[i][j] >= 3) {
volume += (result / m[i][j]);
for (int p = 0; p < 5; p++) {
for (int q = 0; q < 5;q++)
if (tempVisited[p][q] == 1)
visited[p][q] = 1;
}
}
}
}
}
return volume;
}
public void copyArray(int[][] t, int[][] s) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
t[i][j] = s[i][j];
}
}
}
public void solution() {
ArrayList<Integer> ans = new ArrayList<>();
for (int i = 0; i < K; i++) {
answer = 0;
int get = 0;
int[][] newMap = new int[5][5];
int turnCnt = 3;
ArrayList<int[]> deletedPoints = new ArrayList<>();
// 여기서 부터는 중심점을 하나 잡고 회전하게 됨
for (int j = 1; j < 4; j++) {
for (int k = 1; k < 4; k++) {
for (int l = 0; l < 3; l++) {
turnSetta(maps, k, j);
int t = calcMystery(maps);
if (get < t) {
get = t;
turnCnt = l;
deletedPoints.clear();
copyArray(newMap, maps);
for (int p = 0; p < 5; p++) {
for (int q = 0; q < 5; q++) {
if (visited[p][q] == 1)
deletedPoints.add(new int[] {p, q});
}
}
} else if (get > 0 && get == t && turnCnt > l) {
turnCnt = l;
deletedPoints.clear();
copyArray(newMap, maps);
for (int p = 0; p < 5; p++) {
for (int q = 0; q < 5; q++) {
if (visited[p][q] == 1)
deletedPoints.add(new int[] {p, q});
}
}
}
}
turnSetta(maps, k, j);
}
}
if (get == 0)
break;
answer += get;
// 최대였던 유적지 지도로 변경
copyArray(maps, newMap);
deletedPoints.sort(((o1, o2) -> {
return o1[1] == o2[1] ? o2[0] - o1[0] : o1[1] - o2[1];
}));
// 유적지 유물번호 변경
for (int j = 0; j < deletedPoints.size(); j++) {
int cx = deletedPoints.get(j)[0];
int cy = deletedPoints.get(j)[1];
maps[cx][cy] = newNumber.poll();
}
while (true) {
int t = calcMystery(maps);
if (t == 0)
break;
else if (t > 0) {
answer += t;
deletedPoints.clear();
for (int p = 0; p < 5; p++) {
for (int q = 0; q < 5; q++) {
if (visited[p][q] == 1)
deletedPoints.add(new int[] {p, q});
}
}
deletedPoints.sort(((o1, o2) -> {
return o1[1] == o2[1] ? o2[0] - o1[0] : o1[1] - o2[1];
}));
// 유적지 유물번호 변경
for (int j = 0; j < deletedPoints.size(); j++) {
int cx = deletedPoints.get(j)[0];
int cy = deletedPoints.get(j)[1];
maps[cx][cy] = newNumber.poll();
}
}
}
ans.add(answer);
}
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i) + " ");
}
}
public void solve() throws IOException {
input();
solution();
}
public static void main(String[] args) throws IOException {
new Main().solve();
}
}
작업 단위로 함수로 잘 나누고, SRP처럼 하나의 함수가 하나의 책임을 갖도록 하자. 그래야지 나중에 디버깅할 때 편하게 할 수 있다. 또, Java에서 배열 복사를 할 때는 for문으로 직접해야 하기 때문에 위의 코드처럼 copyArray()와 같은 함수를 정의해두면 편하다. 마지막으로 변화 과정을 위해 배열 출력을 해야할 때도 특정 지점에서 for문을 계속 사용하지 말고 printArray()와 같은 함수로 배열 내용을 출력하도록 하는 함수를 정의해두면 편하다.
추천글
https://www.codetree.ai/ko/frequent-problems/problems/ancient-ruin-exploration/description
삼성 코딩테스트 기출 문제 설명: 고대 문명 유적 탐사 | 코드트리
삼성전자 코딩테스트 기출 문제 고대 문명 유적 탐사의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.
www.codetree.ai
'알고리즘' 카테고리의 다른 글
| 코드트리 - 마법의 숲 탐색 (Java) (2) | 2025.04.23 |
|---|---|
| 프로그래머스 - N으로 표현 (0) | 2025.04.22 |
| 백준 - 빌런 호석 22251 (3) | 2025.03.24 |
| 백준 - 줄세우기 2631 (2) | 2025.03.19 |
| 백준 - 경사로 14890 (2) | 2025.03.19 |
