[백준] #2564 경비원

 문제

 

[문제 링크]

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

2564번: 경비원

 

[문제]

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

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

그림1

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

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

 

[입력]

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 블록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

 

[출력]

첫째 줄에 동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력한다.

 

[예제 입출력]

[예제 입력 1 복사]

10 5
3
1 4
3 2
2 8
2 3

[예제 출력 1 복사]

23

 

 

 

 풀이 방법

 

[변수]

w: 가로 길이

h: 세로 길이

n: 상점 개수

locate[]: 상점&동근 방향(동서남북)

distance[]: 상점&동근의 기준 경계로 부터의 거리

min[]: 상점-동근 최단 거리

min[n]: 최단 거리의 합

 

[풀이]

Step1. 가로 길이, 세로 길이, 상점 개수를 입력 받는다.

Step2. 각 상점과 동근이의 위치 정보(방향, 경계로부터의 거리)를 입력한다.

Step3. 동근이와 각 상점 사이의 최단 거리를 계산해준다.

Step3-1. 동근이와 상점의 방향이 같을 때와 아닐 때로 기준을 나눠준다. 만약 같다면 단순히 서로의 거리를 빼서 최단 거리를 구해준다. 이때, 뺀 값이 음수가 나올 수 있으니 Math.abs()를 사용하여 최단 거리를 양수로 바꿔준다.

Step3-2. 만약 동근이와 상점의 방향이 다르다면 먼저 동근이의 방향을 기준으로 조건을 나누고, 그 안에서 각각 상점의 방향을 기준으로 최단 거리를 계산해준다.

Step4. 각 최단 거리를 합하여 출력해준다.

 

 

[+]

Math.abs()

abs() 함수는 인자 값에 대한 절대 값을 반환하는 함수이다. 인자 값의 타입으로는 int, float, long, double 등의 입력이 가능하다. Math 클래스의 함수 중 하나로 static 함수이다.

a= -2일 때 Math.abs(a)를 해주면 2라는 값이 리턴되고, 마찬가지로 b=-3.62일 때는 Math.abs(b)를 해주면 3.62라는 값이 리턴된다. 

 

 

 

 작성 코드

 

import java.lang.*;
import java.util.Scanner;

/*2564*/

public class Guard {
    public static void main(String[] args){

        Scanner sc = new Scanner((System.in));
        int w= sc.nextInt();    //가로 길이
        int h= sc.nextInt();    //세로 길이
        int n= sc.nextInt();    //상점 개수
        int i;
        int locate[] = new int[n+1];  //각 상점과 동근의 방향(동서남북)
        int distance[] = new int[n+1];    //각 상점과 동근의 경계로부터의 거리
        int min[] = new int[n+1];    //최단거리
        min[n]=0;   //최단거리의 합

        //위치 정보 입력
        for(i=0; i<n+1; i++){
            locate[i]=sc.nextInt();
            distance[i]= sc.nextInt();
        }

        //동근이와 상점 사이의 최단 거리
        for(i=0; i<n; i++){
            if(locate[i]==locate[n]){
                min[i]= distance[n]-distance[i];
                if(min[i]<0) min[i] = Math.abs(min[i]);
            }
            else{
                if(locate[n]==1){   //동근이 북
                    if(locate[i]==2){   //상점 남
                        if(distance[i]+distance[n]<w) min[i]=distance[i]+distance[n]+h;
                        else min[i]=(2*w)-(distance[i]+distance[n])+h;
                    }
                    else if(locate[i]==3) min[i]=distance[i]+distance[n];   //상점 서
                    else min[i]=distance[i]+(w-distance[n]);    //상점 동

                }
                else if(locate[n]==2){  //동근이 남
                    if(locate[i]==1){   //상점 북
                        if(distance[i]+distance[n]<w) min[i]=distance[i]+distance[n]+h;
                        else min[i]=(2*w)-(distance[i]+distance[n])+h;
                    }
                    else if(locate[i]==3) min[i]=(h-distance[i])+distance[n];   //상점 서
                    else min[i]=(h-distance[i])+(w-distance[n]);    //상점 동
                }
                else if(locate[n]==3){  //동근이 서
                    if(locate[i]==4){   //상점 동
                        if(distance[i]+distance[n]<h) min[i]=distance[i]+distance[n]+w;
                        else min[i]=(2*h)-(distance[i]+distance[n])+w;
                    }
                    else if(locate[i]==1) min[i]=distance[i]+distance[n];   //상점 북
                    else min[i]=distance[i]+(h-distance[n]);    //상점 남

                }
                else if(locate[n]==4){  //동근이 동
                    if(locate[i]==3){   //상점 서
                        if(distance[i]+distance[n]<h) min[i]=distance[i]+distance[n]+w;
                        else min[i]=(2*h)-(distance[i]+distance[n])+w;
                    }
                    else if(locate[i]==1) min[i]=(w-distance[i])+distance[n];   //상점 북 
                    else min[i]=(w-distance[i])+(h-distance[n]);    //상점 남
                }
            }
        }
        //최단 거리의 합 min[n] 구하기
        for(i=0;i<n;i++){
            min[n]+=min[i]; 
        }
        System.out.println(min[n]);

    }
}