문제출처
https://school.programmers.co.kr/learn/courses/30/lessons/87694
문제 설명
다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.
지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.
단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.
즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.
다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.
한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.
지형을 나타내는 직사각형이 담긴 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 이하인 자연수입니다.
- 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
- 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.
입출력 예
문제풀이
- 컴퓨터가 지나가는 길을 인식하기 위해 현재 값보다 두배 늘려준다.
- 큐에 현재위치와 길이값을 넣어주고 지나간 길은 100을 더해 더이상 지나가지 않게 한다.
- 큐에 값이 있다면 하나씩 빼서 그 값이 원하는 위치와 동일하다면 길이값의 반을 답으로 리턴한다.
- 같지 않다면 동서남북을 거치면서 그 위치값이 0보다 크거나 같고 100보다 작거나 같고 그 값이 지나가지 않은 길이라면 큐에 위치값을 넣어주고 현재 위치에 100을 더해줌으로써 갔던 길을 표시해준다.
BFS로 풀어야 겠다는 건 알았는데 어떻게 구현해야 할 지 모르겠어서 다른 사람 풀이를 봤다ㅠㅠ 간단한 BFS는 구현이 가능한데 조금 난이도가 올라가면 구현에 어려움이 있는 거 같다ㅠㅠ 다른 사람의 문제풀이를 보면서 어떻게 구현해야 하는 지 더 공부해야겠다😥😥ㅠㅠ
참고 코드
function solution(rectangle, characterX, characterY, itemX, itemY) {
let map = Array.from(Array(103).fill(0), ()=> Array(103).fill(0));
let doubleRectangle = rectangle.map(cur => cur.map(point => point*2))
doubleRectangle.forEach(([x1,y1,x2,y2]) => {
for(let i=y1; i<=y2; i++){
for(let j=x1; j<=x2; j++){
if(j ==x1 || j == x2 || i == y1 || i == y2){
if(map[j][i] == 1) continue;
else map[j][i] += 1;
}else{
map[j][i] += 2;
}
}
}
})
characterX *=2;
characterY *=2;
itemX *= 2;
itemY *= 2;
const directionX = [1, -1, 0, 0];
const directionY = [0, 0, 1, -1];
const queue = [[characterX, characterY, 0]];
map[characterX][characterY] += 100;
while(queue.length){
const [currentX, currentY, count] = queue.shift();
if(currentX == itemX && currentY == itemY){
return count/2;
}
for(let i=0; i<4; i++){
const [nX, nY] = [currentX + directionX[i], currentY + directionY[i]];
if(nX >= 0 && nX < 101 && nY >=0 && nY < 101){
if(map[nX][nY] == 1){
map[nX][nY] += 100;
queue.push([nX, nY, count+1]);
}
}
}
}
} 