백준 - 경비원

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

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

[문제 설명]

상점까지 모서리를 따라 가는 최소거리의 합

 

[접근 방법]

문제를 보자마자 떠오른 건 BFS였는데 읽어보니까 모서리를 따라서 가야한다는 조건이 있다.

처음엔 단순히 X좌표 Y좌표끼리 연산을 하면 모든 경우의 수를 처리할 수 있을 줄 알았는데 맞은 편에 있을 때만 성립한다는 걸 알았다.

따라서, 맞은 편에 있을 때와 나머지 경우의 수로 나눠서 풀어야 한다.

이 문제를 풀면서 아쉬웠던 점이, 맞은 편에 있는 조건을 하드코딩으로 짰다는 게 아쉽다.

문제 조건이 북:1 남:3 동:2 서:4 이런 식이었으면 두 좌표의 방향 값의 차의 절댓값이 2면 건너 편이라고 처리하면 좋았을텐데

북:1 남:2 서:3 동:4라 그냥 둘다 조건문을 줬다.

시간복잡도는 O(N)이 될듯.

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 br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int lengthOfColumn = Integer.parseInt(st.nextToken());
        int lengthOfRow = Integer.parseInt(st.nextToken());
        int cntOfShops = Integer.parseInt(br.readLine());
        int roundOfMap = 2*lengthOfRow+2*lengthOfColumn;
        // 가게 좌표랑 마지막은 경비병 좌표
        // 0은 방향, 1은 row, 2는 column
        int[][] positionOfShopsAndGuard = new int[cntOfShops+1][3];
        for (int i = 0; i <= cntOfShops; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int side = Integer.parseInt(st.nextToken());
            positionOfShopsAndGuard[i][0] = side;
            switch (side) {
                case 1 :
                    positionOfShopsAndGuard[i][1] = 0;
                    positionOfShopsAndGuard[i][2] = Integer.parseInt(st.nextToken());
                    break;
                case 2 :
                    positionOfShopsAndGuard[i][1] = lengthOfRow;
                    positionOfShopsAndGuard[i][2] = Integer.parseInt(st.nextToken());
                    break;
                case 3 :
                    positionOfShopsAndGuard[i][1] = Integer.parseInt(st.nextToken());
                    positionOfShopsAndGuard[i][2] = 0;
                    break;
                case 4 :
                    positionOfShopsAndGuard[i][1] = Integer.parseInt(st.nextToken());
                    positionOfShopsAndGuard[i][2] = lengthOfColumn;
                    break;
            }
        }

        int sum = 0;
        // 1: 북, 2: 남, 3: 서, 4: 동
        for (int i = 0; i < cntOfShops; i++) {
            int[] guard = positionOfShopsAndGuard[positionOfShopsAndGuard.length-1];
            // 상점과 경비원이 맞은 편에 있는 경우
            int length = 0;
            // 북 남 듀오
            if ((guard[0] == 1 && positionOfShopsAndGuard[i][0] == 2) || (guard[0] == 2 && positionOfShopsAndGuard[i][0] == 1)){
                length = guard[2]+positionOfShopsAndGuard[i][2]+lengthOfRow;
                length = Math.min(length, Math.abs(roundOfMap-length));
            }
            // 동 서 듀오
            else if ((guard[0] == 3 && positionOfShopsAndGuard[i][0] == 4) || (guard[0] == 4 && positionOfShopsAndGuard[i][0] == 3)) {
                length = guard[1]+ positionOfShopsAndGuard[i][1]+lengthOfColumn;
                length = Math.min(length, Math.abs(roundOfMap-length));
            }
            // 일직선이거나 수직선 듀오
            else {
                length = Math.abs(guard[1]-positionOfShopsAndGuard[i][1])+Math.abs(guard[2]-positionOfShopsAndGuard[i][2]);
            }

            sum += length;
        }

        System.out.println(sum);
    }
}