[알고리즘, 코드트리] 고대 문명 유적 탐사 - java

문제

문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

요약하자면 아래와 같다. 총 다섯 가지 동작을 수행해야 한다.

(1) 탐사 진행. 3 X 3 격자를 90도, 180도, 270도 회전시킬 수 있다.

(2) 이 때, 얻을 수 있는 가장 높은 순위의 유물을 획득한다.

(3) 유물을 획득하면 해당 격자는 비어있게 되는데 이 때, 벽면에 써있는 유물의 번호를 주어진 순서대로 채운다.

(4) 연쇄 반응을 통해 유물을 획득할 수 있다.

(5) 위 (1) ~ (4) 과정을 Q번 반복한다.

(6) 어떠한 방법을 사용하더라도 유물을 획득할 수 없었다면 모든 탐사는 그 즉시 종료된다. 이 경우 얻을 수 있는 유물이 존재하지 않음으로, 종료되는 턴에 아무 값도 출력하지 않는다.

입력

첫 번째 줄에 탐사의 반복 횟수 K와 벽면에 적힌 유물 조각의 개수 M이 공백을 사이에 두고 주어집니다.

그 다음 5개의 줄에 걸쳐 유물의 각 행에 있는 유물 조각에 적혀 있는 숫자들이 공백을 사이에 두고 순서대로 주어집니다.

그 다음 줄에는 벽면에 적힌 M개의 유물 조각 번호가 공백을 사이에 두고 순서대로 주어집니다.

단, 초기에 주어지는 유적지에서는 탐사 진행 이전에 유물이 발견되지 않으며, 첫 번째 턴에서 탐사를 진행한 이후에는 항상 유물이 발견됨을 가정해도 좋습니다.

• 1≤K≤10
• 10≤M≤300
• 1≤ 유물 조각 번호 ≤7

출력

첫 번째 줄에 각 턴 마다 획득한 유물의 가치의 총합을 공백을 사이에 두고 출력합니다.

문제 풀이

자료구조 정의 및 입출력

static int[][] map = new int[5][5];
static int[] pieceArr;
static int pieceIdx = 0;
static int[] dx = new int[] {1,0,-1,0};
static int[] dy = new int[] {0,1,0,-1};

지도는 5 X 5 사이즈 고정이다. 자료구조에서 특별히 눈에 띄는 것은 없다.

K = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());   

for(int y = 0; y < 5; y++) {
    st = new StringTokenizer(br.readLine());
    for(int x = 0; x < 5; x++) {
        map[y][x] = Integer.parseInt(st.nextToken());
    }
}

pieceArr = new int[M];
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < M; i++) {
    pieceArr[i] = Integer.parseInt(st.nextToken());
}

입출력으로 map과 pieceArr을 초기화해주고 본격적으로 구조를 생각해 보자.

int result = 0;
int maxScore = Integer.MIN_VALUE;
int[][] maxMap = new int[5][5];

while(K-- > 0) {
    // 회전각 0:90도, 1: 180도, 2: 270도
    for(int angle = 2; angle >= 0; angle--) {
        // 우선순위 때문에 순서 거꾸로
        for(int x = 3; x >= 1; x--) {
            for(int y = 3; y >= 1; y--) {
            	// (x, y)에서 돌리기
                int[][] temp = spin(y, x);
                // 3개 이상 뭉쳐있는 유물수 확인하기
                int score = getItem();
                
                // score가 지금까지 최솟값보다 같거나 크다면 temp, maxScore 기억
                if(score >= maxScore) {
                	
                }
            }
        }
    }
	
    // 연쇄반응으로 얻을 수 있는 총 유물 확인하기
    result = chainReact(maxMap);
    maxScore = 0;
    if(result == 0) {
        break;
    }
    sb.append(result).append(" ");
}
System.out.println(sb);

문제에서 우선순위를 조금 복잡하게 설정하였다. 우선순위를 결정하는 순위는 아래와 같다. 이를 주의해서 확인해 보자.

(1) 유물 1차 획득 가치

(2) 회전한 각도가 가장 적은 방법

(3) 회전 중심 좌표의 열(x)이 가장 작은 구간

(4) 회전 중심 좌표의 행(y)이 가장 작은 구간

 

따라서 코드의 우선순위 표현은 아래와 같이 했다.

for(int angle = 2; angle >= 0; angle--) {
    // 우선순위 때문에 순서 거꾸로
    for(int x = 3; x >= 1; x--) {
        for(int y = 3; y >= 1; y--) {
        
            int[][] temp = spin(y, x, angle);
            int score = getItem(temp);
            // score가 지금까지 최솟값보다 같거나 크다면 temp, maxScore 기억
            if(score >= maxScore) {
                maxScore = score;
                maxMap = temp;
            }
        }
    }
}

이 반복문 구조라면 계산한 유물의 값이 같을 때, 계산 순서에 의해 자동으로 우선순위가 높은 상황이 덮어 씌워지게 된다.

3 X 3 격자 회전 _ spin()

static private int[][] spin (int y, int x, int angle) {
    int[][] temp = new int[5][5];
    for(int i = 0 ; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            temp[i][j] = map[i][j];
        }
    }

    Queue<Integer> q = new ArrayDeque();
    q.add(map[y - 1][x - 1]);
    q.add(map[y - 1][x]);
    q.add(map[y - 1][x + 1]);
    q.add(map[y][x + 1]);
    q.add(map[y + 1][x + 1]);
    q.add(map[y + 1][x]);
    q.add(map[y + 1][x - 1]);
    q.add(map[y][x - 1]);

    int nextY = 0, nextX = 0, d = 0;
    if(angle == 2) {
        nextY = y + 1;
        nextX = x - 1;
        d = 3;
    } else if(angle == 1) {
        nextY = y + 1;
        nextX = x + 1;
        d = 2;
    } else if(angle == 0) {
        nextY = y - 1;
        nextX = x + 1;
        d = 1;
    }

    temp[nextY][nextX] = q.poll();
    int nowY = nextY;
    int nowX = nextX;
    while(!q.isEmpty()) {
        nextY = nowY + dy[d];
        nextX = nowX + dx[d];
        if(nextY < y - 1 || nextY > y + 1 || nextX < x - 1 || nextX > x + 1) {
            d = (d + 1) % 4;
            continue;
        }
        temp[nextY][nextX] = q.poll();
        nowY = nextY;
        nowX = nextX;
    }

    return temp;
}

main 함수에서 브루트포스로 격자를 모두 회전시킬 것이다. 따라서 spin 함수에서는 돌릴 격자의 중심 좌표인 y와 x뿐만 아니라 얼마나 돌릴지에 대한 정보인 angle을 함께 입력받아야 한다.

 

돌리는 방법은 아래와 같다.

Start를 기준으로 Queue에 시계 방향대로 돌아가는 숫자를 집어넣는다.

Queue<Integer> q = new ArrayDeque();
q.add(map[y - 1][x - 1]);
q.add(map[y - 1][x]);
q.add(map[y - 1][x + 1]);
q.add(map[y][x + 1]);
q.add(map[y + 1][x + 1]);
q.add(map[y + 1][x]);
q.add(map[y + 1][x - 1]);
q.add(map[y][x - 1]);

 

꺼낼 때는 돌리는 angle에 의해 시작점의 좌표만 계산해주면 된다. 시작점의 좌표를 구했으면 다시 시계방향으로 Queue에서 숫자를 꺼내어 집어넣는다.

int nextY = 0, nextX = 0, d = 0;
if(angle == 2) {
    nextY = y + 1;
    nextX = x - 1;
    d = 3;
} else if(angle == 1) {
    nextY = y + 1;
    nextX = x + 1;
    d = 2;
} else if(angle == 0) {
    nextY = y - 1;
    nextX = x + 1;
    d = 1;
}

temp[nextY][nextX] = q.poll();
int nowY = nextY;
int nowX = nextX;
while(!q.isEmpty()) {
    nextY = nowY + dy[d];
    nextX = nowX + dx[d];
    if(nextY < y - 1 || nextY > y + 1 || nextX < x - 1 || nextX > x + 1) {
        d = (d + 1) % 4;
        continue;
    }
    temp[nextY][nextX] = q.poll();
    nowY = nextY;
    nowX = nextX;
}

복잡해 보여도 원리를 이해하면 쉬우니 한번 해보자.

유물을 확인 _ getItem()

격자의 회전이 끝났다면 그 상황에서 유물의 총가치를 확인해야 한다.

static private int getItem(int[][] temp) {
    boolean[][] visit = new boolean[5][5];

    int result = 0;
    for(int y = 0; y < 5; y++) {
        for(int x = 0; x < 5; x++) {
            if(!visit[y][x]) {
                result += bfs(y, x, temp, visit);
            }
        }   
    }

    return result;
}

3개 이상 뭉쳐있는 유물의 판별은 bfs를 통해서 한다.

유물 계산

static private int bfs(int y, int x, int[][] temp, boolean[][] visit) {
    Queue<int[]> q = new ArrayDeque<>();
    Queue<int[]> q2 = new ArrayDeque<>();
    q.add(new int[] {y, x});
    q2.add(new int[] {y, x});
    visit[y][x] = true;
    int pivot = temp[y][x];

    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int d = 0; d < 4; d++) {
            int nextY = now[0] + dy[d];
            int nextX = now[1] + dx[d];

            if(nextY < 0 || nextY >=5 || nextX < 0 || nextX >= 5) {
                continue;
            }
            if(visit[nextY][nextX]) {
                continue;
            }
            if(temp[nextY][nextX] != pivot) {
                continue;
            }

            q.add(new int[] {nextY, nextX});
            q2.add(new int[] {nextY, nextX});
            visit[nextY][nextX] = true;
        }
    }

    int result = q2.size(); 
    if(result >= 3) {
        while(!q2.isEmpty()) {
            int[] now = q2.poll();
            temp[now[0]][now[1]] = 0;
        }
    }

    return result >= 3 ? result : 0;
}

현 단계에서는 2차원 지도를 0으로 바꿔주는 과정은 필요 없지만, 추후에 있을 연쇄 반응에 getItem()과 bfs()를 재사용하기 위해서 작성해 두었다.

연쇄 반응 _ chainReaction()

유물의 최대가치를 얻을 수 있는 방법을 찾았다면 연쇄반응을 통해 총 몇의 가치의 유물을 찾을 수 있는지 확인한다.

static private int chainReact(int[][] maxMap) {
    boolean flag = true;
    int total = 0;
    while(flag) {
        flag = false;

        int value = getItem(maxMap);

        total += value;
        if(value != 0) {
            flag = true;
        }
        init(maxMap);
    }
    return total;
}

더 이상 value를 얻을 수 없을 때까지 getItem()을 수행한다. 또한,  getItem()을 수행할 때마다 maxMap에는 0으로 구멍이 생기게 되므로 init으로 주어진 유물을 순서에 맞게 채워준다.

격자를 채우자 _ init()

static private void init(int[][] maxMap) {
    for(int x = 0; x < 5; x++) {
        for(int y = 4; y >= 0; y--) {
            if(maxMap[y][x] == 0) {
                maxMap[y][x] = pieceArr[pieceIdx++];
            }
        }
    }

    map = maxMap;
}

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int[][] map = new int[5][5];
    static int[] pieceArr;
    static int pieceIdx = 0;
    static int[] dx = new int[] {1,0,-1,0};
    static int[] dy = new int[] {0,1,0,-1};

    static int K, M;

    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();

        K = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());   

        for(int y = 0; y < 5; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x = 0; x < 5; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        pieceArr = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < M; i++) {
            pieceArr[i] = Integer.parseInt(st.nextToken());
        }

        int result = 0;
        int maxScore = Integer.MIN_VALUE;
        int[][] maxMap = new int[5][5];

        while(K-- > 0) {
            // 회전각 0:90도, 1: 180도, 2: 270도
            for(int angle = 2; angle >= 0; angle--) {
                // 우선순위 때문에 순서 거꾸로
                for(int x = 3; x >= 1; x--) {
                    for(int y = 3; y >= 1; y--) {
                        int[][] temp = spin(y, x, angle);
                        int score = getItem(temp);
                        // score가 지금까지 최솟값보다 같거나 크다면 temp, maxScore 기억
                        if(score >= maxScore) {
                            maxScore = score;
                            maxMap = temp;
                        }
                    }
                }
            }

            result = chainReact(maxMap);
            maxScore = 0;
            if(result == 0) {
                break;
            }
            sb.append(result).append(" ");
        }
        System.out.println(sb);
    }

    static private int[][] spin (int y, int x, int angle) {
        int[][] temp = new int[5][5];
        for(int i = 0 ; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                temp[i][j] = map[i][j];
            }
        }

        Queue<Integer> q = new ArrayDeque();
        q.add(map[y - 1][x - 1]);
        q.add(map[y - 1][x]);
        q.add(map[y - 1][x + 1]);
        q.add(map[y][x + 1]);
        q.add(map[y + 1][x + 1]);
        q.add(map[y + 1][x]);
        q.add(map[y + 1][x - 1]);
        q.add(map[y][x - 1]);

        int nextY = 0, nextX = 0, d = 0;
        if(angle == 2) {
            nextY = y + 1;
            nextX = x - 1;
            d = 3;
        } else if(angle == 1) {
            nextY = y + 1;
            nextX = x + 1;
            d = 2;
        } else if(angle == 0) {
            nextY = y - 1;
            nextX = x + 1;
            d = 1;
        }

        temp[nextY][nextX] = q.poll();
        int nowY = nextY;
        int nowX = nextX;
        while(!q.isEmpty()) {
            nextY = nowY + dy[d];
            nextX = nowX + dx[d];
            if(nextY < y - 1 || nextY > y + 1 || nextX < x - 1 || nextX > x + 1) {
                d = (d + 1) % 4;
                continue;
            }
            temp[nextY][nextX] = q.poll();
            nowY = nextY;
            nowX = nextX;
        }

        return temp;
    }

    static private int getItem(int[][] temp) {
        boolean[][] visit = new boolean[5][5];

        int result = 0;
        for(int y = 0; y < 5; y++) {
            for(int x = 0; x < 5; x++) {
                if(!visit[y][x]) {
                    result += bfs(y, x, temp, visit);
                }
            }   
        }

        return result;
    }

    static private int bfs(int y, int x, int[][] temp, boolean[][] visit) {
        Queue<int[]> q = new ArrayDeque<>();
        Queue<int[]> q2 = new ArrayDeque<>();
        q.add(new int[] {y, x});
        q2.add(new int[] {y, x});
        visit[y][x] = true;
        int pivot = temp[y][x];

        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int d = 0; d < 4; d++) {
                int nextY = now[0] + dy[d];
                int nextX = now[1] + dx[d];

                if(nextY < 0 || nextY >=5 || nextX < 0 || nextX >= 5) {
                    continue;
                }
                if(visit[nextY][nextX]) {
                    continue;
                }
                if(temp[nextY][nextX] != pivot) {
                    continue;
                }

                q.add(new int[] {nextY, nextX});
                q2.add(new int[] {nextY, nextX});
                visit[nextY][nextX] = true;
            }
        }

        int result = q2.size(); 
        if(result >= 3) {
            while(!q2.isEmpty()) {
                int[] now = q2.poll();
                temp[now[0]][now[1]] = 0;
            }
        }
        
        return result >= 3 ? result : 0;
    }

    static private void init(int[][] maxMap) {
        for(int x = 0; x < 5; x++) {
            for(int y = 4; y >= 0; y--) {
                if(maxMap[y][x] == 0) {
                    maxMap[y][x] = pieceArr[pieceIdx++];
                }
            }
        }

        map = maxMap;
    }

    static private int chainReact(int[][] maxMap) {
        boolean flag = true;
        int total = 0;
        while(flag) {
            flag = false;

            int value = getItem(maxMap);
            
            total += value;
            if(value != 0) {
                flag = true;
            }
            init(maxMap);
        }
        return total;
    }
}

소요 시간 : 2시간 10분