NHN OPEN TALK DAY 문제풀이

Area.java

package project;

public class Area {
    private int num; // 지역 번호
    private int x; // 중심의 x 좌표
    private int y; // 중심의 y 좌표
    private int radius; // 반지름

    private enum Location {
        ANOTHER_LOCATION, INSIDE, OUTSIDE
    }

    public Area(int num, int x, int y, int radius) {
        this.num = num;
        this.x = x;
        this.y = y;
        this.radius = radius;
    }

    public int getNum() {
        return num;
    }

    private boolean checkOverlap(Area target) {
        double distance = Math.sqrt(Math.pow(Math.abs(this.x - target.x), 2)
                + Math.pow(Math.abs(this.y - target.y), 2));

        return (distance <= this.radius + target.radius);
    }

    // 상하좌우 좌표를 비교해 내부에 지역간 포함 관계를 확인한다
    public Location checkLocation(Area target) {
        if (((this.x + this.radius > target.x + target.radius)
                && (this.x - this.radius < target.x - target.radius)
                && (this.y + this.radius > target.y + target.radius)
                && (this.y - this.radius < target.y - target.radius))) {
            return Location.INSIDE;
        } else if (((this.x + this.radius < target.x + target.radius)
                && (this.x - this.radius > target.x - target.radius)
                && (this.y + this.radius < target.y + target.radius)
                && (this.y - this.radius > target.y - target.radius))) {
            return Location.OUTSIDE;
        } else if ((this.num != target.num) && checkOverlap(target)) {
            // 원형 담이 서로 닿지 않는다는 조건에 어긋나는 경우
            System.out.println(-1);
            System.exit(0);
        }

        return Location.ANOTHER_LOCATION;
    }

    public boolean checkInclusion(Area target) {
        return checkLocation(target) == Location.INSIDE;
    }
}

Jailbreak.java

package project;

import java.util.Arrays;
import java.util.Scanner;

public class Jailbreak {
    private static final int AREA_INFO_COUNT = 4; // 구역 당 주어지는 정보 개수
    private static int[][] areasLocation; // 지역의 좌표 정보
    private static int[][] areas; // 지역의 인접 행렬

    public static void main(String[] args) {
        Jailbreak jailbreak = new Jailbreak();
        Scanner in = new Scanner(System.in);

        int areaCount = in.nextInt() + 1; // 전체 지역 개수
        areasLocation = new int[areaCount][AREA_INFO_COUNT];
        areasLocation[0] = new int[]{0, 5000, 5000, 10000};

        for (int i = 1; i < areasLocation.length; i++) {
            for (int j = 0; j < AREA_INFO_COUNT; j++) {
                areasLocation[i][j] = in.nextInt();
            }
        }

        Arrays.sort(areasLocation, (a1, a2) -> a2[3] - a1[3]); // 넓이 순으로 정렬

        int start = in.nextInt(); // 출발 구역 번호
        int end = in.nextInt(); // 도착 구역 번호
        areas = jailbreak.initAreas(areaCount);

        String answer = new RouteFinder(areas).search(start, end);
        System.out.println(answer);
    }

    // 지역간 연결 여부를 확인해 2차원 배열을 초기화한다
    private int[][] initAreas(int areaCount) {
        areas = new int[areaCount][areaCount];

        for (int i = 0; i < areas.length; i++) {
            Area outside = getArea(i);

            for (int j = i; j < areas.length; j++) {
                Area inside = getArea(j);

                if (i != j) {
                    connectInternalArea(outside, inside);
                    blockConnection(areaCount, outside, inside);
                }
            }
        }

        return areas;
    }

    // 내부에 포함된 지역과 연결한다
    private void connectInternalArea(Area outside, Area inside) {
        int outIdx = outside.getNum();
        int inIdx = inside.getNum();

        if (outside.checkInclusion(inside)) {
            areas[outIdx][inIdx] = 1;
            areas[inIdx][outIdx] = 1;
        }
    }

    // 직접 맞닿지 않은 지역과의 연결을 끊는다
    private void blockConnection(int areaCount, Area outside, Area inside) {
        int outIdx = outside.getNum();
        int inIdx = inside.getNum();

        for (int k = 0; k < areaCount; k++) {
            Area target = getArea(k);

            if ((k != outIdx) && ((outside.checkInclusion(target) && target.checkInclusion(inside)))) {
                areas[outIdx][inIdx] = 0;
            }

            areas[inIdx][outIdx] = areas[outIdx][inIdx];
        }
    }

    private Area getArea(int index) {
        return new Area(areasLocation[index][0], areasLocation[index][1]
                , areasLocation[index][2], areasLocation[index][3]);
    }
}

RouteFinder.java

package project;

import java.util.LinkedList;
import java.util.Queue;

public class RouteFinder {
    private int[][] areas;

    public RouteFinder(int[][] areas) {
        this.areas = areas;
    }

    public String search(int start, int end) {
        String path = "";
        Queue<Node> queue = new LinkedList<>();
        boolean[] visitStatus = new boolean[areas.length];

        try {
            queue.add(new Node(start, path));

            while (!queue.isEmpty()) {
                Node queueVal = queue.poll();

                if (queueVal.num == end) {
                    path = queueVal.path;
                    break;
                }

                for (int i = 0; i < areas.length; i++) {
                    if (areas[queueVal.num][i] == 1 && !visitStatus[i]) {
                        queue.add(new Node(i, queueVal.path));
                        visitStatus[i] = true;
                    }
                }
            }
        } catch (IllegalStateException e) {
            path = "-1";
        }

        return path;
    }

    private class Node {
        private int num;
        private String path;

        Node(int num, String path) {
            this.num = num;
            this.path = path.equals("") ? ("" + num) : (path + " " + num);
        }
    }
}

석호필_탈옥.md

문제 해결 절차

1. 문제의 그림에서 지역은 원으로 표현되어 있지만, 서로 닿지 않는다는 조건이 있기 때문에 ◇ 모양으로 바꿔서 생각할 수 있습니다.
2. 지역 별로 동서남북 4개의 좌표를 비교해 포함 관계를 파악합니다. 이를 바탕으로 서로 연결된 지역이면 1, 연결되지 않았다면 0을 할당하는 2차원 배열을 만듭니다.
3. 인접 행렬에 BFS를 적용해 목적지까지의 최단 경로를 찾습니다.