SWEA D5 4112 이상한 피라미드 탐험

SWEA D5 4112 이상한 피라미드 탐험

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=G3fO2N5Zi_s&feature=youtu.be

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 5. 5.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH
 * @mem
 * @time
 * @caution
 */
public class SWEA_D5_4112_이상한피라미드탐험 {

    static int[] levels;
    static Point[] points = new Point[4];

    private static int TC;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        levels = new int[143];
        for (int i = 1; i < levels.length; i++) {
            levels[i] = 1 + i * (i - 1) / 2;
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));

        TC = Integer.parseInt(br.readLine());
        for (int t = 1; t <= TC; t++) {
            int answer = 0;
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(tokens.nextToken());
            int b = Integer.parseInt(tokens.nextToken());
            if (a != b) {
                if (a > b) {
                    int temp = a;
                    a = b;
                    b = temp;
                }
                answer = bfs(a, b);
            }
            sb.append("#").append(t).append(" ").append(answer).append("\n");
        }
        System.out.println(sb);
    }

    static int bfs(int low, int high) {
        boolean[] visited = new boolean[10013];
        int highLevel = Arrays.binarySearch(levels, high);
        if (highLevel < 0) {
            highLevel = (-highLevel - 1) - 1;
        }
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(high, highLevel, 0));
        visited[high] = true;

        while (!q.isEmpty()) {
            Point front = q.poll();
            if (front.num == low) {
                return front.depth;
            }

            // 갈 수 있는 4곳의 경계를 살펴보자.
            Arrays.fill(points, null);
            points[0] = isIn(front.level, front.num - 1) ? new Point(front.num - 1, front.level, front.depth + 1) : null;
            points[1] = isIn(front.level, front.num + 1) ? new Point(front.num + 1, front.level, front.depth + 1) : null;

            points[2] = isIn(front.level - 1, front.num - front.level) ? new Point(front.num - front.level, front.level - 1, front.depth + 1) : null;
            points[3] = isIn(front.level - 1, front.num - front.level + 1) ? new Point(front.num - front.level + 1, front.level - 1, front.depth + 1) : null;

            for (int i = 0; i < points.length; i++) {
                if (points[i] != null && !visited[points[i].num]) {
                    q.offer(points[i]);
                    visited[points[i].num] = true;
                }
            }
        }
        return -1;
    }

    static boolean isIn(int level, int num) {
        int left = levels[level];
        int right = left + level - 1;
        return left <= num && num <= right;
    }


    static class Point {
        int num, level, depth;

        public Point(int num, int level, int depth) {
            this.num = num;
            this.level = level;
            this.depth = depth;
        }

        @Override
        public String toString() {
            return " [n=" + num + ", l=" + level + ", d=" + depth + "]";
        }
    }


    private static String src = "3\r\n" +
                                "5 2\r\n" +
                                "7 7\r\n" +
                                "100 1000";


}