[백준] 2564 - 경비원 (자바/Java)

문제

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

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

< 그림 1 >

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

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

입력

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

출력

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

---

큰 박스를 하나의 이차원 배열로 생각하고, 각각의 좌표를 다음과 같이 정의하였다.

북서쪽 모서리를 (0,0)으로 두고, 동쪽과 서쪽은 값이 커질수록 row값이 커지며, 북쪽과 남쪽은 값이 커질수록 col값이 커지는 것으로 이해하였다.

그렇게 각각의 경우의 수를 좌표로 나타내면 아래의 그림과 같다.

그렇게 가게의 좌표와, 동근이의 좌표를 각각 설정하였고, 가게의 좌표는 배열에 담아 두었다.

나중에 방향을 검사하기 위해 방향 또한 배열의 2번째 인덱스에 넣었다.

// 가상의 이차원 배열을 상상, 왼쪽 위가 0,0
		// 북, 남은 col이 변함
		// 동, 서는 row가 변함 
		for (int i = 0; i < N; i++) {
			int row = 0;
			int col = 0;
			int dir = sc.nextInt();
			switch (dir) {
			case 1: // 북
				row = 0; 
				col = sc.nextInt();
				break;
			case 2: // 남
				row = by; // box의 세로 길이
				col = sc.nextInt();
				break;
			case 3: // 서
				row = sc.nextInt();
				col = 0;
				break;
			case 4: // 동
				row = sc.nextInt();
				col = bx; // box의 가로 길이
				break;
			}
			arr.add(new int[] { row, col, dir });
		}

		int dongdir = sc.nextInt();
		int dongr = 0;
		int dongc = 0;
		switch (dongdir) {
		case 1: // 북
			dongr = 0;
			dongc = sc.nextInt();
			break;
		case 2: // 남
			dongr = by;
			dongc = sc.nextInt();
			break;
		case 3: // 서
			dongr = sc.nextInt();
			dongc = 0;
			break;
		case 4: // 동
			dongr = sc.nextInt();
			dongc = bx;
			break;
		}

경우의 수는 다음과 같다.

1. 가게와 동근이가 같은 방향에 있는 경우
2. 가게와 동근이가 다른 방향에 있는 경우
   1. 가게와 동근이가 마주보고 있는 경우 (북-남, 동-서)
   2. 가게와 동근이가 90도 차이가 나는 경우 (북-서, 북-동, 남-서 등)

처음에는 이 경우의 수를 각각 처리하려고 하였는데, 결국은 1과 2-2는 row와 col 값의 차이를 구한다는 점에서 같은 경우의 수로 봐도 무방하였다. 1은 두 좌표 중 하나의 좌표의 차이가 0이지만, 그 정도 연산은 간단하기 때문에 코드를 깔끔하게 구현하기 위해서 같은 경우로 처리하였다.

그래서 2-1만 if문으로 처리하고, 나머지는 else로 row와 col 값의 차이의 절대값을 구하는 과정으로 하였다.

			else {
				// 90도 차이 : 두 좌표의 절댓값차이
				// 같은 줄에 있을 대도 절댓값 차이
				sum += Math.abs(shop[0] - dongr);
				sum += Math.abs(shop[1] - dongc);
			}

		}

2-1의 경우, 북-남으로 마주보고 있는 경우는 박스의 세로값을 더해주고, 시계방향과 반시계방향 중 작은 값을 더해주어야 한다.

문제 예시에 나와있는 것처럼 북-남으로 마주볼때, 남쪽에서 시계방향으로 가는 경우는 각각의 col 좌표를 더해주면 된다.

그리고 반시계방향으로 가는 경우는 가로 길이(bx)에서 각각의 col 좌표를 뺀 값을 더해주어야 한다.

이 중 작은 값을 선택하여 sum에 더하였다.

		int sum = 0;
		for (int[] shop : arr) {
			if (dongdir + shop[2] == 3 || dongdir + shop[2] == 7) {
				// 서로 마주보는 경우 180도 차이
				// dong이 남이나 북에 있을 경우
				if (dongdir == 1 || dongdir == 2) {
					sum += Math.min(dongc + shop[1], 2 * bx - (dongc + shop[1]));
					sum += by;
				} else {
					// dong이 동이나 서에 있을 경우
					sum += bx;
					sum += Math.min(dongr + shop[0], 2 * by - (dongr + shop[0]));
				}

			}

이렇게 하면 모든 경우의 수 처리가 가능하다

 

---

전체 코드

package BOJ0809;

import java.util.ArrayList;
import java.util.Scanner;

public class BOJ_2564_경비원 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int bx = sc.nextInt(); // 가로
		int by = sc.nextInt(); // 세로
		int N = sc.nextInt();
		ArrayList<int[]> arr = new ArrayList<>(); // shop의 위치와 방향을 담을 배열

		// 가상의 이차원 배열을 상상, 왼쪽 위가 0,0
		// 북, 남은 col이 변함
		// 동, 서는 row가 변함 
		for (int i = 0; i < N; i++) {
			int row = 0;
			int col = 0;
			int dir = sc.nextInt();
			switch (dir) {
			case 1: // 북
				row = 0; 
				col = sc.nextInt();
				break;
			case 2: // 남
				row = by; // box의 세로 길이
				col = sc.nextInt();
				break;
			case 3: // 서
				row = sc.nextInt();
				col = 0;
				break;
			case 4: // 동
				row = sc.nextInt();
				col = bx; // box의 가로 길이
				break;
			}
			arr.add(new int[] { row, col, dir });
		}

		int dongdir = sc.nextInt();
		int dongr = 0;
		int dongc = 0;
		switch (dongdir) {
		case 1: // 북
			dongr = 0;
			dongc = sc.nextInt();
			break;
		case 2: // 남
			dongr = by;
			dongc = sc.nextInt();
			break;
		case 3: // 서
			dongr = sc.nextInt();
			dongc = 0;
			break;
		case 4: // 동
			dongr = sc.nextInt();
			dongc = bx;
			break;
		}

		int sum = 0;
		for (int[] shop : arr) {
			if (dongdir + shop[2] == 3 || dongdir + shop[2] == 7) {
				// 서로 마주보는 경우 180도 차이
				// dong이 남이나 북에 있을 경우
				if (dongdir == 1 || dongdir == 2) {
					sum += Math.min(dongc + shop[1], 2 * bx - (dongc + shop[1]));
					sum += by;
				} else {
					// dong이 동이나 서에 있을 경우
					sum += bx;
					sum += Math.min(dongr + shop[0], 2 * by - (dongr + shop[0]));
				}

			} else {
				// 90도 차이 : 두 좌표의 절댓값차이
				// 같은 줄에 있을 대도 절댓값 차이
				sum += Math.abs(shop[0] - dongr);
				sum += Math.abs(shop[1] - dongc);
			}

		}
		System.out.println(sum);

	}

}