문제

https://school.programmers.co.kr/learn/courses/30/lessons/87694

---

입력

• 지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle
• 초기 캐릭터의 위치 characterX, characterY
• 아이템의 위치 itemX, itemY

---

출력

• 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리

---

풀이

제한조건

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
• 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
• 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
• charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
• 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• itemX, itemY는 1 이상 50 이하인 자연수입니다.
• 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

접근방법

단순 탐색

x, y축에 너무 빠지지 말자.
x,y축이 생각과 달라도, 원점의 위치가 생각과 달라도 늘 하던대로 생각해서 접근하면 된다.

단순 탐색으로 해결가능한 문제다.
CCW같은 방법으로도 접근 가능해보이나, BFS를 통한 단순 탐색이 가장 쉬워 보인다.

요약

1. 주어진 사각형을 board에 그려본다.
2. 외곽선을 따라 탐색한다.

외곽선을 따라 이동하는것이 이 문제의 핵심이다.
단순 BFS에서 여기가 외곽선인지 어떻게 알 수 있을까.

문제를 살펴보면, 사각형이 최대 4개 밖에 주어지지 않는다.
따라서 각 지점에서 현재 지점이 특정 사각형의 내부인지 확인해주는 작업만 하면 된다.

// 전체 사각형을 순회하며 내부 지점인지 확인한다.
public boolean isInRectangle(int x, int y, int[][] rectangle) {
	for (int[] data : rectangle)
		if (data[0] * 2 < x && x < data[2] * 2 && data[1] * 2 < y && y < data[3] * 2)
				return true;
	return false;
}

그럼 단순 탐색으로 찾을 수 있다.

여기서 주의할점은 좌표값을 2배로 확장해서 생각해야한다.
입력 예시에서와 같은 상황을 생각해보자.

좌표값을 2배로 확장해서 생각하지 않는다면

화살표로 표시된 지점에서 사각형을 따라 둘러 가야하지만,
board 상에서는 연결된 지점인것 처럼 표현되기 때문에 최단 거리가 달라진다.

---

코드

import java.util.*;

class Solution {
	int SIZE = 104;
	int[][] board = new int[SIZE][SIZE];
	int[][] visit = new int[SIZE][SIZE];
	int[] dx = {-1, 1, 0, 0};
	int[] dy = {0, 0, -1, 1};

	public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
		for (int[] data : rectangle)
			draw(data);

		Queue<int[]> q = new ArrayDeque<>();
		visit[characterX * 2][characterY * 2] = 1;
		q.add(new int[] {characterX * 2, characterY * 2});
		while (!q.isEmpty()) {
			int[] cur = q.poll();

			for (int d = 0; d < 4; ++d) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				if (board[nx][ny] == 1 && !isInRectangle(nx, ny, rectangle) && visit[nx][ny] == 0) {
					q.add(new int[] {nx, ny});
					visit[nx][ny] = visit[cur[0]][cur[1]] + 1;
				}
			}
		}
		return (visit[itemX * 2][itemY * 2] - 1) / 2;
	}

	// 전체 사각형을 순회하며 내부 지점인지 확인한다.
	public boolean isInRectangle(int x, int y, int[][] rectangle) {
		for (int[] data : rectangle)
			if (data[0] * 2 < x && x < data[2] * 2 && data[1] * 2 < y && y < data[3] * 2)
				return true;
		return false;
	}

	// board에 사각형을 그린다.
	private void draw(int[] data) {
		int fixedX1 = data[0] * 2;
		int fixedY1 = data[1] * 2;
		int fixedX2 = data[2] * 2;
		int fixedY2 = data[3] * 2;

		for (int i = fixedX1; i <= fixedX2; ++i) {
			board[i][fixedY1] = 1;
			board[i][fixedY2] = 1;
		}
		for (int i = fixedY1; i <= fixedY2; ++i) {
			board[fixedX1][i] = 1;
			board[fixedX2][i] = 1;
		}
	}
}