[프로그래머스] 위클리 챌린지 11주차 (javascript)

문제 ❓

위클리 챌린지 11주차

풀이 방법

좌표에 따라 사각형을 입력하는데 자잘한 조건을 제외한 큰 조건들을 살펴보면

• 좌표 간의 거리가 1차이 나지만 연결되지 않았을 경우
• 테두리가 중복될 경우

두 가지를 중점적으로 생각해야 한다.

이 두가지 조건을 고려하며 생각한 풀이과정은 다음과 같다.

1. 행과 열의 최대 사이즈 (문제 제한사항: 50) * 2의 크기의 2차원 배열을 선언후 0으로 초기화
2. 매개 변수로 받은 모든 좌표에 2를 곱하여 저장
3. 좌표가 입력된 배열을 돌며 테두리에 1을 내부에는 2를 더해줌 (테두리를 입력시 이미 저장된 값이 1(테두리)이면 pass)
4. BFS를 실행하여 목표지점까지의 최단거리를 구하고 2로 나눈값을 반환

코드

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;

총평

사각형을 채우는 과정에서 3중 반복문을 사용해 board의 길이가 커지거나 입력된 좌표사이의 길이가 커질 경우 시간초과가 날 수도 있을 것 같다. 후에 다른 사람들의 코드를 참고하여 최적화를 시켜봐야겠다..