백준 - 2564번(경비원)

문제 출처: https://www.acmicpc.net/problem/2564

---

문제

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

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

< 그림 1 >

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

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

---

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int M = Integer.parseInt(tokenizer.nextToken());
        int N = Integer.parseInt(tokenizer.nextToken());
        int storeCount = Integer.parseInt(reader.readLine());
        int result = 0;

        int[][] map = new int[storeCount][2];

        // 1: 북, 2: 남, 3: 서, 4: 동

        // 상점 위치
        for (int i = 0; i < storeCount; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < 2; j++) {
                map[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        // 동근이 위치
        tokenizer = new StringTokenizer(reader.readLine());
        int dong_i = Integer.parseInt(tokenizer.nextToken());
        int dong_j = Integer.parseInt(tokenizer.nextToken());

        int mod = 0; // 0: 위, 1: 아래, 2: 왼쪽, 3: 오른쪽
        int left = 0, right = 0; // 양 사이드
        int opposite = 0; // 반대

        switch (dong_i) {
            case 1:
                mod = 1;
                left = 4;
                right = 3;
                opposite = 2;
                break;

            case 2:
                mod = 0;
                left = 3;
                right = 4;
                opposite = 1;
                break;

            case 3:
                mod = 2;
                left = 1;
                right = 2;
                opposite = 4;
                break;

            case 4:
                mod = 3;
                left = 2;
                right = 1;
                opposite = 3;
                break;
        }

        for (int i = 0; i < storeCount; i++) {
            int location = map[i][0];
            int value = map[i][1];

            if (location == dong_i) {
                result += Math.abs(dong_j - value);
            } else if (location == left) { // 동근이 기준 왼쪽
                switch (location) {
                    case 1:
                        result += value + dong_j;
                        break;

                    case 2:
                        result += (M - value) + (N - dong_j);
                        break;

                    case 3:
                        result += (N - value) + dong_j;
                        break;

                    case 4:
                        result += value + (M - dong_j);
                        break;
                }
            } else if (location == right) {
                switch (location) {
                    case 1:
                        result += (M - value) + dong_j;
                        break;

                    case 2:
                        result += value + (N - dong_j);
                        break;

                    case 3:
                        result += dong_j + value;
                        break;

                    case 4:
                        result += (N - value) + (M - dong_j);
                        break;
                }
            } else if (location == opposite) {
                result += Math.min(value + dong_j, (M - value) + (M - dong_j));
                switch (location) {
                    case 1:
                    case 2:
                        result += N;
                        break;

                    case 3:
                    case 4:
                        result += M;
                        break;
                }
            }
        }

        System.out.println(result);
    }

}

---

• 고려해야 할 조건이 상당히 많은 문제였다.
• 동근이의 위치에 따라 진행방향이 달랐는데, 공통적인 처리는 현위치의 좌, 우에 위치한 상점은 최소 탐색 방향이 정해져있으므로 바로 계산하고, 반대 방향의 경우 시계방향과 시계반대 방향 중 짧은 것을 선택한다.
• 동, 서, 남, 북 4방향의 위치를 고려하여 왼쪽, 오른쪽, 반대 방향 위치를 정해주는 작업이 조금 번거로웠다.
• 이 문제도 난이도에 비해 들어간 시간이 많은 것 같다.