[백준/Java] 25644번 : 경비원

✏️ 문제 분석

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

 

블록의 가로, 세로 길이, 상점 위치, 동근이의 위치가 주어질 때

동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력하라.

✏️ 구현 아이디어

블록의 경계선을 따라 이동하므로 1차원 거리로 치환하여 처리할 수 있다.

시계방향으로 직사각형 경계를 따라 각 위치의 1차원 거리를 계산한다. (북, 동, 남, 서)

동근이 위치와 가게 위치 사이의 최단 거리는 '두 거리의 차이' 또는 '전체 둘레-두 거리의 차이' 중 더 작은 값이다.

✏️ 알고리즘

구현

✏️ 시간 복잡도

최단 거리 계산하는 과정에서 시간 복잡도는 O(N)이다. N은 최대 100이므로 시간 안에 연산 가능하다.

✏️ 코드 설계

1. 입력 받기
2. 직사각형 전체 둘레 total 계산
3. 각 가게 위치를 1차원 거리로 변환
4. 가게와 동근이 거리 계산하여 min값 구하기
5. 모두 합한 값을 출력

✏️ 정답 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int total = 2*(w+h);

        int n = Integer.parseInt(br.readLine());
        int[] store = new int[n+1];

        for(int i=0; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            int dir = Integer.parseInt(st.nextToken());
            int len = Integer.parseInt(st.nextToken());
            //1북 2남 3서 4동
            switch(dir){
                case 1: store[i] = len; break;
                case 4: store[i] = w + len; break;
                case 2: store[i] =  w + h + (w-len); break;
                case 3: store[i] = w + h + w + (h-len); break;
            }
        }

        int ans = 0;
        for(int i=0; i<n; i++){
            int len = Math.abs(store[i] - store[n]);
            ans += Math.min(len, total-len);
        }
        System.out.println(ans);
    }

}

✏️ Note

• 입력 범위가 작아서 dfs로 풀려고 했다가 실패한 문제이다.
• 직사각형 둘레를 1로 입력하고 동근이 좌표에서 가게 좌표로 도달하는 최단경로를 계산하려고 했었다.
• 그런데 둘레를 1차원으로 펼쳐서 생각하니 쉽게 풀리는 문제였다. 🤨