[백준]JAVA - 2564번: 경비원

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

2564번: 경비원

풀이

동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하면 된다.

해당 문제에서 동근이가 상점으로 갈 수 있는 경로는 시계 방향, 반시계 방향 2가지가 존재한다.

 

동서남북으로 이루어진 직사각형 모양의 맵을 일직선으로 가정하고 풀면 쉽게 해결할 수 있다.

좌측 상단(0, 0) 부터 시작해서 시계방향으로 이어서 일직선으로 생각해준다.

 

일직선으로 가정했다면 최단 거리를 계산할 때 쉬워질 수 있다.

동근이와 각 상점 사이의 거리(시계 방향)와 일직선 총 거리에서 동근이와 각 상점 사이의 거리를 뺏을 때의 값(반시계 방향)을 비교해서 더 작은 값이 최단 거리이다.

 

동서남북으로 이루어진 맵을 일직선으로 변환시키는 과정은 아래와 같다.

switch (dir) {
case 1:
    len[i] = value;
    break;
			
case 2:
    len[i] = C + R + (C-value);
    break;
				
case 3:
    len[i] = 2*C + R + (R-value);
    break;
				
case 4:
    len[i] = C + value;
    break;
}

 

총 길이를 100이라고 가정했을 때, 동근이와 상점 A의 거리(시계 방향)는 75라면 반시계 방향의 거리는 25이다. 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int C = Integer.parseInt(st.nextToken()); // 가로
        int R = Integer.parseInt(st.nextToken()); // 세로
		
        int storeCnt = Integer.parseInt(br.readLine());
        int[] len = new int[storeCnt+1];
		
        for (int i=0; i<=storeCnt; i++) {
            st = new StringTokenizer(br.readLine());
			
            int dir = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
			
            switch (dir) {
            case 1:
                len[i] = value;
                break;
			
            case 2:
                len[i] = C + R + (C-value);
                break;
				
            case 3:
                len[i] = 2*C + R + (R-value);
                break;
				
            case 4:
                len[i] = C + value;
                break;
            }
        }
		
        int guard = len[storeCnt];
        int ans = 0;
        for (int i=0; i<storeCnt; i++) {
            int target = len[i];
			
            int oneWay = Math.abs(guard - target);
            int twoWay = 2*R + 2*C - oneWay;
			
            ans += Math.min(oneWay, twoWay);
        }
		
        System.out.println(ans);
    }
}