Algorithm
[CodeKata] 프로그래머스: 10.24(일), 아이템 줍기(11주차)
ttaeng_99
2021. 10. 25. 02:27
반응형
🥋 Oooth More!! (Level 3)
🧮 풀이
최단경로를 탐색하므로 BFS를 사용해야함은 알았으나, 구체적인 이동방법을 구현하기가 어려워 모범답안을 학습했다.
🖇 리뷰
function solution(rectangle, characterX, characterY, itemX, itemY) {
const xmoves = [1, -1, 0, 0];
const ymoves = [0, 0, 1, -1];
// 최대 범위가 50이지만 좌표간의 거리를 생각해 2배 증가시킴
const maxSize = 101;
const board = Array.from({ length: maxSize }, () => Array(maxSize).fill(0));
const newRect = rectangle.map((el) => el.map((v) => v * 2));
newRect.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 (board[j][i] === 1) continue;
// 그러나, 현재 값이 테두리 이지만 저장된 값이 테두리가 아닐경우 +1
// (0일때는 1이 되고 1 이상일 때는 테두리가 아니므로 값이 저장되어 지나갈 수 없다.)
else board[j][i] += 1;
} else board[j][i] += 2;
}
}
});
// 모든 좌표 2배 증가
characterX *= 2;
characterY *= 2;
itemX *= 2;
itemY *= 2;
// 최단 거리이므로 bfs 실행
const q = [[characterX, characterY, 0]];
board[characterX][characterY] += 100;
while (q.length) {
const [nowX, nowY, price] = q.shift();
// 목표 지점에 도착했을 경우 (결과값 / 2) 를 반환
if (nowX === itemX && nowY === itemY) return price / 2;
for (let i = 0; i < 4; i++) {
const [nX, nY] = [nowX + xmoves[i], nowY + ymoves[i]];
if (checkLoc(nX, nY))
if (board[nX][nY] === 1) {
board[nX][nY] += 100;
q.push([nX, nY, price + 1]);
}
}
}
}
// 다음 좌표가 범위 안인지 검사
const checkLoc = (x, y) => x >= 0 && x < 101 && y >= 0 && y < 101;
1. Board 세팅
- xmoves, ymoves의 각 인덱스는, 노드가 동서남북으로 움직이는 각 경우에 해당한다.
- 그리고, 전체 크기의 2배(문제 제한사항 50 * 2) 를 한 board를 만든다. 이는, 그림처럼 1칸 차이지만 이어져 있지 않은 경로이동을 방지하기 위함이다. 그렇기에, 모든 조건을 2배로 치환한 뒤, 경로값의 절반을 정답으로 반환한다.
- newRect 역시, rectangle의 각 좌표들을 2배씩 map() 맵핑한 배열이다.
- 이를 순회하며, board에 경로를 그려준다. i가 y좌표(y1, y2) 와 같거나, j가 x좌표(x1, x2) 와 같다면 경로에 해당한다. 이 때, 이미 경로(1)일 경우엔 continue, 아니라면 board 해당좌표를 1로 채워준다.
- 경로가 아니라면, 사각형 내부에 해당하므로 이 때는 board 해당좌표를 2로 채워준다.
- board가 2배로 확대됬으므로, 캐릭터(characterX, characterY), 아이템(itemX, itemY) 좌표 역시 2배로 치환한다.
2. Board 탐색(BFS)
- BFS 탐색을 위한 큐(queue)배열 q를 선언한다. 큐에 담기는 요소는, [x좌표, y좌표, 이동거리] 배열형태로 담는다.
- board의 방문좌표에 대해서는 +100 처리를 해서, 다음에 이동하지 않도록 막는다.
- 그리고, q(큐)가 빌때까지 BFS탐색을 지속한다. 큐에 담긴 맨 앞의 요소를 꺼내온다. (shift())
- 이 요소의 x좌표(nowX), y좌표(nowY)가 아이템 좌표와 같은 경우, 이동거리(price)의 절반값을 정답으로 반환한다.
- 아니라면, 현재(nowX, nowY)의 상하좌우로 이동가능한지 탐색한다. checkLoc() 함수는 board를 벗어나는지, board[nx][ny]가 경계선(1)인지 각각 if로 판정한다.
- 이동이 된다면 해당좌표도 +100 처리해서 재이동을 막고, q(큐)에 새 요소로 추가한다. 이 때, 이동거리는 +1한다.
반응형