[BaekJoon] 3678 카탄의 개척자 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/3678

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int SIZE = 10_000; // 최대 크기

    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    // 10000번째까지 육각형 타일에 숫자를 채울 것인데, 이를 나타낼 2차원 배열
    //  - 육각형을 채워나가다보면 큰 육각형으로 둘러싸이는 것을 알 수 있다
    //      - 1: 두 번째부터 7번쨰까지 큰 육각형은 크기가 2인 육각형에 둘러싸인다
    //      - 2: 8번째부터 19번째까지 큰 육각형은 크기가 3인 육각형에 둘러싸인다
    //      - 각 큰 육각형은 6N개의 육각형을 가진다
    //  - 이를 생각해보면 1 + sum(6N)만큼 육각형이 필요한 것을 알 수 있다
    //      - 1 + 6 * sum(N) = 1 + 6 * (N(N + 1) / 2) <= 10,000
    //      - 여기서 N을 구해보면 58 정도가 나온다
    //      - 대략 60으로 잡고 행으로는 4배, 열로는 2배 늘린다
    //          - 한 육각형에 대해서 인접한 육각형을 아래와 같이 표현할 것이므로 행으로는 4배, 열로는 2배 늘린다
    //                  (x - 2, y)
    //      (x - 1, y - 1)      (x - 1, y + 1)
    //                    (x, y)
    //      (x + 1, y - 1)      (x + 1, y + 1)
    //                  (x + 2, y)
    static int[][] map = new int[240][120];
    // n번째 타일의 숫자
    static int[] answer = new int[SIZE + 1];
    // 각 자원 숫자가 몇 번 나왔는지를 나타내는 배열
    static int[] numberCnt = new int[6];
    static int[] dx = {-2, -1, 1, 2, 1, -1};
    static int[] dy = {0, -1, -1, 0, 1, 1};

    static int nthTile;

    static void input() {
        nthTile = scanner.nextInt();
    }

    static void solution() {
        sb.append(answer[nthTile]).append('\n');
    }

    static void makeMap() {
        int x = 120; // 시작 지점 행 좌표
        int y = 60; // 시작 지점 열 좌표
        int index = 1; // n번째 타일에 숫자를 채워야하는데, 여기서 n을 의미

        map[x][y] = 1; // 시작 위치는 1부터 시작하므로 1을 넣고 시작
        numberCnt[1]++; // 1이 사용되었으니 사용 횟수에 1 추가
        answer[index++] = 1; // index번째(1번째) 숫자로 1을 넣고 시작

        // 육각형을 채워가다보면 새로운 큰 육각형이 시작될 때, n번째 육각형이라고 한다면
        // 시작 위치에서 위로 n - 1번만큼 올라감
        // 이를 나타내줄 변수
        int size = 1;

        while(index <= SIZE) {
            // 이전 큰 육각형에서 다음 큰 육각형으로 이동할 때, dx[5], dy[5]만큼 움직이게 된다
            // 그래서 우선 dx[5], dy[5]만큼 움직여 새로운 큰 육각형의 시작 위치로 이동한다
            x += dx[5];
            y += dy[5];
            // 해당 위치의 자원 숫자를 구한다
            int nextNum = getNextNum(x, y);

            // 해당 위치에 자원 숫자를 배치하고 이용된 자원 숫자의 수를 1 증가시킨다
            // 또한 index번째 육각형에 자원 숫자를 배치한다
            map[x][y] = nextNum;
            numberCnt[nextNum]++;
            answer[index++] = nextNum;

            // 현재 큰 육각형을 현재 위치부터 이동해보며 큰 육각형을 채워간다
            for(int idx = 0; idx < 6; idx++) {
                 // size만큼 움직이며 육각형을 채워간다
                for(int cnt = 0; cnt < size; cnt++) {
                    // 처음 위로 올라갈 때에는 size - 1번만큼 이동하므로
                    // 처음 위로 올라갈 때에 size - 1번만큼 이동했다면 for문을 빠져나간다
                    if(idx == 0 && cnt == size - 1) {
                        continue;
                    }
                    // 채우는 육각형이 SIZE번째보다 크다면 더이상 채워야할 필요가 없으니 채우지 않는다
                    if(index > SIZE) break;

                    // 현재 방향으로 한 칸 이동한다
                    x += dx[idx];
                    y += dy[idx];
                    // 이동한 위치의 자원 숫자를 구한다
                    nextNum = getNextNum(x, y);
                    // 구한 자원 숫자를 이동한 위치에 배치하고 이용된 자원 숫자의 수를 1 증가시킨다
                    // 또한 index번째 육각형에 자원 숫자를 배치한다
                    map[x][y] = nextNum;
                    numberCnt[nextNum]++;
                    answer[index++] = nextNum;
                }
            }

            // 큰 육각형의 사이즈가 1씩 커지기 때문에 size를 1 증가시킨다
            size++;
        }
    }

    static int getNextNum(int x, int y) {
        // 현재 위치의 인접한 위치들이 어떤 자원 숫자를 배치하고 있는지 확인한다
        int[] usedNums = new int[6];
        for(int idx = 0; idx < 6; idx++) {
            usedNums[map[x + dx[idx]][y + dy[idx]]] = 1;
        }

        // 현재 위치에 배치할 자원 숫자를 찾는다
        //  인접한 위치들에서 사용되지 않은 숫자들 중 가장 적게 사용한 숫자, 그 중 가장 번호가 작은 것을 찾는다
        int minCnt = Integer.MAX_VALUE;
        int minNum = 0;
        for(int idx = 1; idx < 6; idx++) {
            if(usedNums[idx] == 0 && numberCnt[idx] < minCnt) {
                minCnt = numberCnt[idx];
                minNum = idx;
            }
        }

        return minNum;
    }

    public static void main(String[] args) {
        makeMap();

        int T = scanner.nextInt();

        while(T-- > 0) {
            input();
            solution();
        }

        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}