오늘은 프로그래머스에서 깊이/너비 우선 탐색 문제 중 아이템 줍기 문제 풀이를 해보겠습니다. 오늘도 사용 언어는 바로 JavaScript입니다. 그럼 아이템 줍기 문제 풀이 함께 해보러 가시죠.
프로그래머스 > 깊이/너비 우선 탐색(DFS/BFS) > 아이템 줍기 문제 풀이
∂ 문제 정보
문제명: 아이템 줍기
문제 난이도: Level 3
문제 푼 사람 수: 764명
사용 가능 언어: 6개 (JavaScript 사용)
∂ 문제 설명
다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.
지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.
단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.
즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.
다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.
한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.
프로그래머스 아이템 줍기 문제는 정말 깁니다. 제가 지금까지 풀었던 문제 중 가장 그림도 많고 내용도 많은 것 같습니다. 이번 아이템 줍기 문제 풀이를 위해 위의 내용을 요약해보도록 하겠습니다.
직사각형으로 이루어진 지형의 바깥 테두리의 길을 통해 캐릭터가 아이템을 줍기 위해 이동해야하는 가잘 짧은 거리 구하기
Inputs
rectangle: 지형을 나타내는 직사각형 리스트 (2차원 배열)
characterX: 초기 캐릭터의 위치 X 좌표
characterY: 초기 캐릭터의 위치 Y 좌표
itemX: 아이템의 위치 X 좌표
itemY: 아이템의 위치 Y 좌표
Output: 직사각형 바깥 테두리 길을 통해 캐릭터가 아이템을 줍기 위해 이동할 가장 짧은 거리
∂ 제한 사항
º rectangle의 세로(행) 길이는 1 이상 4 이하입니다. º rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다. º 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다. º 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다. º 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다. º characterX, characterY는 1 이상 50 이하인 자연수입니다. º 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다. º itemX, itemY는 1 이상 50 이하인 자연수입니다. º 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다. º 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.
º 전체 배점의 50%는 직사각형이 1개인 경우입니다. º 전체 배점의 25%는 직사각형이 2개인 경우입니다. º 전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.
1 ≤ 직사각형의 개수(rectangle의 길이) ≤ 4
직사각형 = [좌측 하단 X, 좌측 하단 Y, 우측 상단 X, 우측 상단 Y]로 구성
1 ≤ 직사각형 좌표 (X, Y) ≤ 50
서로 다른 직사각형의 X, Y 좌표가 같은 경우는 없다.
꼭지점, 선이 겹치거나 분리 or 포함하는 직사각형은 주어지지 않는다.
1 ≤ characterX, characterY ≤ 50
캐릭터 위치는 직사각형으로 만들어진 바깥 테두리 위의 한 점이다.
1 ≤ itemX, itemY ≤ 50
아이템 위치는 직사각형으로 만들어진 바깥 테두리 위의 한 점이다.
캐릭터와 아이템의 위치는 같지 않다.
테스트 케이스 중 50%는 직사각형 1개
테스트 케이스 중 25%는 직사각형 2개
테스트 케이스 중 25%는 직사각형 3개 or 4개
∂ 입출력 예
ractangle
characterX
characterY
itemX
itemY
result
[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]]
1
3
7
8
17
[[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]]
9
7
6
1
11
[[1,1,5,7]]
1
1
4
7
9
[[2,1,7,5],[6,4,10,10]]
3
1
7
10
15
[[2,2,5,5],[1,3,6,4],[3,1,4,6]]
1
4
6
3
10
∂ 입출력 예 설명
입출력 예 #1
캐릭터 위치는 (1, 3)이며, 아이템 위치는 (7, 8)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.
입출력 예 #2
캐릭터 위치는 (9, 7)이며, 아이템 위치는 (6, 1)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.
입출력 예 #3
캐릭터 위치는 (1, 1)이며, 아이템 위치는 (4, 7)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.
입출력 예 #4, #5 설명 생략
위에 충분히 많은 예에 대한 설명이 있었지만, 이해를 돕기 위해 아이템 줍기 문제 풀이의 입출력 예 #4, #5에 대한 추가 설명을 하겠습니다.
입출력 예 #4
입출력 예 #5
∂ 알고리즘 만들기
1. 캐릭터 시작 위치부터 아이템 위치까지 너비 우선 탐색(BFS)로 길을 탐색 시작한다. 2. 이동 거리는 0.5로 하여 탐색한다. 3. 이동한 위치가 이미 방문한 위치인지, 실제 길 위인지 확인 후 이동한다. 3-1. 직사각형 선 위에 있으면서, 모든 직사각형의 안에 포함되지 않는 위치인지 확인한다.
위 아이템 줍기 문제 풀이 알고리즘은 간단해 보이지만, 두 가지 키 포인트를 갖고 있습니다.
이동 거리는 0.5로 하여 탐색한다.
이동 거리를 0.5로 탐색하는 이유는 직사각형 내부를 통과하는지, 직사각형 밖으로 이동하는지를 파악하기 위한 방법입니다. 실제 이동한 위치는 직사각형들 밖의 길이지만, 이동한 길이 직사각형을 통과하는 길일 수도 있는 점을 확인하기 위한 조치입니다.
이동한 위치가 ... 실제 길 위인지 확인 후 이동한다.
실제 길 위인지 판단하는 방법은 직사각형의 테두리 위에 있으며, 그 위치가 모든 직사각형의 안에 포함되지 않는 위치여야합니다.
위 두 가지 키 포인트를 활용하여 알고리즘을 만들어보았으며, 알고리즘을 토대로 아래 JavaScript 아이템 줍기 코드를 구현을 하였습니다.
∂ 코드 구현
function solution(rectangle, characterX, characterY, itemX, itemY) {
var answer;
// 1. 캐릭터 시작 위치부터 아이템 위치까지 너비 우선 탐색(BFS)로 길을 탐색 시작한다.
goItemToGet(characterX, characterY);
function goItemToGet(curX, curY, count = 0) {
const visited = [];
const queue = [];
// 2. 이동 거리는 0.5로 하여 탐색한다.
const direction = [[0, 0.5], [0, -0.5], [0.5, 0], [-0.5, 0]];
queue.push([characterX, characterY, 0]);
visited[[characterX, characterY]] = true;
while (queue.length > 0) {
const [curX, curY, curCount] = queue.shift();
if (curX === itemX && curY === itemY) {
answer = curCount/2;
break;
}
for (let j = 0; j < direction.length; j++) {
const [nextX, nextY] = [curX + direction[j][0], curY + direction[j][1]];
// 3. 이동한 위치가 이미 방문한 위치인지, 실제 길 위인지 확인 후 이동한다.
if (!visited[[nextX, nextY]] && isOnRectangleLine(nextX, nextY)) {
visited[[nextX, nextY]] = true;
queue.push([nextX, nextY, curCount + 1]);
}
}
}
}
function isOnRectangleLine(x, y, rect = undefined) {
let isOnRect = false;
for (let i = 0; i < rectangle.length; i++) {
// 3-1. 직사각형 선 위에 있으면서, 모든 직사각형의 안에 포함되지 않는 위치인지 확인한다.
if (x >= rectangle[i][0] && x <= rectangle[i][2] && y >= rectangle[i][1] && y <= rectangle[i][3] && !isInRectangle(x, y)) {
isOnRect = true;
}
}
return isOnRect;
}
function isInRectangle(x, y) {
let isInRect = false;
for(let i = 0; i < rectangle.length; i++) {
if(x > rectangle[i][0] && x < rectangle[i][2] && y > rectangle[i][1] && y < rectangle[i][3]) {
isInRect = true;
break;
}
}
return isInRect;
}
return answer;
}
∂ 채점 결과
아이템 줍기 문제 풀이 채점 결과는 정확성 테스트 케이스 30개 모두 통과하여 문제 풀이를 마치겠습니다.
댓글