[CodeKata] 프로그래머스: 10.24(일), 아이템 줍기(11주차)

🥋 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;

* 출처 : https://velog.io/@seok1007/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9C%84%ED%81%B4%EB%A6%AC-%EC%B1%8C%EB%A6%B0%EC%A7%80-11%EC%A3%BC%EC%B0%A8-javascript  

 

 

1. Board 세팅

• xmoves, ymoves의 각 인덱스는, 노드가 동서남북으로 움직이는 각 경우에 해당한다.
• 그리고, 전체 크기의 2배(문제 제한사항 50 * 2) 를 한 board를 만든다. 이는, 그림처럼 1칸 차이지만 이어져 있지 않은 경로이동을 방지하기 위함이다. 그렇기에, 모든 조건을 2배로 치환한 뒤, 경로값의 절반을 정답으로 반환한다.

* 출처 : https://velog.io/@front/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%95%84%EC%9D%B4%ED%85%9C-%EC%A4%8D%EA%B8%B0-%EC%9C%84%ED%81%B4%EB%A6%AC-%EC%B1%8C%EB%A6%B0%EC%A7%80-11%EC%A3%BC%EC%B0%A8

 

• 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한다.