백준 2564번 경비원 :: 마이구미

이 글은 백준 알고리즘 문제 2564번 "경비원" 을 풀이한다.

정올 출제 문제로써, 풀이 방법은 문제 이해를 통한 단순한 구현이다.

문제 링크 - https://www.acmicpc.net/problem/2564

동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.

예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.

1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.

블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오

문제는 간단하다.

점과 점 사이의 거리를 구하면 된다.

거리를 구하기 위해서는 직사각형의 테두리인 변을 기준으로만 이동할 수 있다.

이동하는 경우는 크게 2가지로 나뉜다.

먼저 하나의 변을 기준으로 인접한 두 변으로 이동하는 경우에는 그 방향으로 이동하면 된다.

하지만 마주보는 변의 경우에는 왼쪽 방향 또는 오른쪽 방향 중 어떤 방향이 최단 거리인지 장담할 수 없다.

즉, 인접한 변의 경우에는 간단히 동수와 상점간의 차이로 구할 수 있다.

마주보는 변의 경우에는 두 방향을 고려해야하기 때문에, 간단한 수학 능력만 있으면 구현할 수 있다.

다음 그림은 마주보는 변의 경우 하나의 예를 표현한다.

 

우리는 마주보는 변으로 이동할 경우에 대해 파악하고 있다면, 문제를 쉽게 해결할 수 있다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2007/2564.java

private void solve() {
    int r = sc.nextInt();
    int c = sc.nextInt();
    int n = sc.nextInt();
    ArrayList<Point> list = new ArrayList<Point>();
 
    for (int i = 0; i < n; i++) {
        int dir = sc.nextInt();
        int dis = sc.nextInt();
        Point p = new Point(dir, dis, c, r);
        list.add(p);
    }
 
    int d = sc.nextInt();
    int v = sc.nextInt();
    Point dong = new Point(d, v, c, r);
    int temp = 0;
    int ans = 0;
 
    if (d == 1) {
        temp = 2;
    } else if (d == 2) {
        temp = 1;
    } else if (d == 3) {
        temp = 4;
    } else {
        temp = 3;
    }
 
    for(Point p : list) {
        if (p.direction == temp) {
            if (p.direction == 1 || p.direction == 2) {
                ans += Math.min(dong.y + p.y + dong.x + p.x, dong.y + p.y + r - dong.x + r - p.x);
            } else {
                ans += Math.min(c - dong.y + c - p.y + dong.x + p.x, dong.y + p.y + dong.x + p.x);
            }
        } else {
            ans += Math.abs(dong.y - p.y) + Math.abs(dong.x - p.x);
        }
    }
    System.out.println(ans);
}
 
static class Point {
    int direction;
    int y;
    int x;
 
    Point(int direction, int distance, int c, int r) {
        this.direction = direction;
 
        if (direction == 1) {
            this.y = 0;
            this.x = distance;
        } else if (direction == 2) {
            this.y = c;
            this.x = distance;
        } else if (direction == 3) {
            this.y = distance;
            this.x = 0;
        } else {
            this.y = distance;
            this.x = r;
        }
    }
}