문제: https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=javascript
문제의 요구사항
지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.
문제의 제한사항
- rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
- rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
- 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
- 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
- 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
- charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
- 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
- itemX, itemY는 1 이상 50 이하인 자연수입니다.
- 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
- 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.
- 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
문제 파악하기
가장 짧은 거리를 return 하도록
가장 짧은 거리를 파악하는데 특화된 알고리즘은 DFS 입니다.
캐릭터는 다각형의 둘레를 통해서 이동합니다.
다각형의 테두리, 내부, 외부 영역의 구분을 통해 캐릭터가 다각형의 둘레를 통해 이동할 수 있도록 만들어 주어야 합니다.
좌표평면을 이중 배열을 통해 만들어 다각형의 테두리를 1, 다각형의 내부를 2, 다각형의 외부를 0으로 만들어,
실제 움직일 수 있는 공간을 1의 값을 가진 좌표로 한정할 예정입니다.
문제에는 명시적으로 나와있지 않아 하나 더 파악해야 하는 부분이 있습니다.
시각적인 부분과 좌표적인 부분에서 발생하는 차이입니다.
위 이미지에서 처음 시작 좌표가 (2, 4) 이고 목표 좌표가 (2, 6) 에 있다고 할 때,
그림 상으로는 아래와 같이 최단 거리를 찾을 수 있습니다.
| 좌표 | 움직인 거리 |
|---|---|
| (2, 4) | |
| (3, 4) | 1 |
| (3, 5) | 2 |
| (2, 5) | 3 |
| (2, 6) | 4 |
하지만 실제 좌표상으로 보면 이보다 더 최단거리로 이동이 가능합니다.
| 좌표 | 움직인 거리 |
|---|---|
| (2, 4) | 0 |
| (2, 5) | 1 |
| (2, 6) | 2 |
이런 차이가 발생하는 이유는 컴퓨터는 다각형의 테두리 좌표만 알 뿐, 다각형이 실제로 어떻게 이어져 있는지는 모르기 때문입니다.
따라서 이 간극을 매꿔주기 위해 좌표와 관련된 모든 값들을 2배로 바꿔주어야 합니다.
문제풀이
function solution(rectangle, characterX, characterY, itemX, itemY) {
var answer = 0;
// 모든 좌표 2배
characterX *= 2;
characterY *= 2;
itemX *= 2;
itemY *= 2;
rectangle = rectangle.map(data => data.map(item => item * 2))
// 이동 방향 설정
const moveX = [1, -1, 0, 0];
const moveY = [0, 0, 1, -1];
// 좌표평면 정의
const rangeSize = 51 * 2;
let range = Array.from({
length: rangeSize
}, () => Array(rangeSize).fill(0));
// 큐 생성
const queue = [{
pos: [characterX, characterY],
count: 0
}];
// 다각형 테두리 = 1
// 다각형 내부 = 2
// 다각형 외부 = 0
rectangle.map( ([x1,y1,x2,y2]) => {
for (let i = x1; i <= x2; i++) {
for (let j = y1; j <= y2; j++) {
if (i === x1 || i === x2 || j === y1 || j === y2) {
// 이미 다각형의 내부(2)로 판단되었다면 테두리로 판단하지 않음
if (range[i][j] === 0) {
range[i][j] = 1;
}
} else {
range[i][j] = 2;
}
}
}
}
)
// 시작 위치 값을 0으로 설정
range[characterX][characterY] = 0;
// DFS
while (queue.length > 0) {
const {pos, count} = queue.shift();
if (pos[0] === itemX && pos[1] === itemY) {
// 모든 좌표값을 2배 했기 때문에 실제 결과값을 2배 감소 처리
return count / 2;
}
for (let i = 0; i < moveX.length; i++) {
const nextX = pos[0] + moveX[i];
const nextY = pos[1] + moveY[i];
// 다각형의 테두리로만 이동하도록 제한
if (range[nextX][nextY] === 1) {
queue.push({
pos: [nextX, nextY],
count: count + 1
})
// 한 번 지나갔던 테두리는 더 이상 지나가지 못하도록 0으로 설정
range[nextX][nextY] = 0;
}
}
}
return answer;
}