[알고리즘] 지게차와 크레인 / JavaScript / 프로그래머스 Lv.2

📖 문제

문제 풀러 가기

문제 설명

A 회사의 물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다. 특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.

최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크레인을 사용하면 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 세로로 4줄, 가로로 5줄이 놓인 창고를 예로 들어보겠습니다. 이때 "A", "BB", "A" 순서대로 해당 종류의 컨테이너 출고 요청이 들어왔다고 가정하겠습니다. “A”처럼 알파벳 하나로만 출고 요청이 들어올 경우 지게차를 사용해 출고 요청이 들어온 순간 접근 가능한 컨테이너를 꺼냅니다. "BB"처럼 같은 알파벳이 두 번 반복된 경우는 크레인을 사용해 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 컨테이너가 꺼내져 3번의 출고 요청 이후 남은 컨테이너는 11개입니다. 두 번째 요청은 크레인을 활용해 모든 B 컨테이너를 꺼냈음을 유의해 주세요. 세 번째 요청이 들어왔을 때 2행 2열의 A 컨테이너만 접근이 가능하고 2행 3열의 A 컨테이너는 접근이 불가능했음을 유의해 주세요.

처음 물류창고에 놓인 컨테이너의 정보를 담은 1차원 문자열 배열 storage와 출고할 컨테이너의 종류와 출고방법을 요청 순서대로 담은 1차원 문자열 배열 requests가 매개변수로 주어집니다. 이때 모든 요청을 순서대로 완료한 후 남은 컨테이너의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 2 ≤ storage의 길이 = n ≤ 50
  • 2 ≤ storage[i]의 길이 = m ≤ 50
    • storage[i][j]는 위에서 부터 i + 1번째 행 j + 1번째 열에 놓인 컨테이너의 종류를 의미합니다.
    • storage[i][j]는 알파벳 대문자입니다.
• 1 ≤ requests의 길이 ≤ 100
  • 1 ≤ requests[i]의 길이 ≤ 2
  • requests[i]는 한 종류의 알파벳 대문자로 구성된 문자열입니다.
  • requests[i]의 길이가 1이면 지게차를 이용한 출고 요청을, 2이면 크레인을 이용한 출고 요청을 의미합니다.

입출력 예

storage	requests	result
["AZWQY", "CAABX", "BBDDA", "ACACA"]	["A", "BB", "A"]	11
["HAH", "HBH", "HHH", "HAH", "HBH"]	["C", "B", "B", "B", "B", "H"]	4

입출력 예 설명

입출력 예 #1

문제 설명의 예시와 같습니다.

입출력 예 #2

창고의 초기 상태와 모든 요청을 수행한 뒤의 상태입니다. 남은 컨테이너의 수인 4를 return 해야 합니다.

---

🧮 풀이

문제의 핵심은 다음과 같습니다.

지게차: requests로 주어진 알파벳을 가진 컨테이너 중 외부 공기와 맞닿아 있는 것들만 제거
크레인: requests로 주어진 알파벳을 가진 컨테이너 모두 제거

따라서 매 request 마다

크레인의 경우 storage 배열을 순회하며 해당 문자를 가진 컨테이너를 전부 제거하면 되고,
지게차의 경우 BFS를 통해 외부 공기를 탐색하고, 해당 문자를 가진 컨테이너 중 외부 공기와 인접한 컨테이너를 제거하면 됩니다.

세 단계에 걸쳐 문제를 해결해보겠습니다. 크레인으로 컨테이너를 꺼내는 과정은 복잡하지 않으니 따로 설명은 생략하고 전체 코드에서 구현하겠습니다.

1️⃣ storage 를 외부 공기로 감싸기

storage를 외부 공기로 감싸는 maps 배열을 생성하여 (0, 0)부터 시작하는 BFS를 실행한다면 외부 공기에 대한 정보를 쉽게 구할 수 있습니다.

let maps = Array.from({ length: n + 2 }, () => Array(m + 2).fill(''));
for (let i = 0; i < n; i++) {
 	for (let j = 0; j < m; j++) {
    	maps[i + 1][j + 1] = storage[i][j];
  	}
}

2️⃣ 외부 공기 탐색하기

앞서 지게차로 컨테이너를 꺼내는 경우 BFS를 통해 외부 공기를 탐색하고, 해당 문자를 가진 컨테이너 중 외부 공기와 인접한 컨테이너를 제거한다고 설명했습니다. 따라서 컨테이너를 제거하기 전에 어느 위치까지 외부 공기인지 파악할 필요가 있습니다.

이를 위해서 BFS(너비 우선 탐색)가 필요합니다. storage를 감싼 외부 공기인 (0, 0)부터 시작하여 maps의 원소가 ''인 구역이 이어진다면 외부 공기라고 판단할 수 있습니다. 다음과 같이 BFS를 수행하여 외부 공기를 true, 내부를 false로 나타내는 배열을 반환합니다.

function getOutside() {
    let visited = Array.from({ length: n + 2 }, () => Array(m + 2).fill(false));
    let queue = [[0, 0]];
    visited[0][0] = true;

    while (queue.length) {
        let [cX, cY] = queue.shift();

        for (let i = 0; i < 4; i++) {
            let [nX, nY] = [cX + dx[i], cY + dy[i]];

            if (
                nX >= 0 &&
                nX < n + 2 &&
                nY >= 0 &&
                nY < m + 2 &&
                !visited[nX][nY] &&
                maps[nX][nY] === ''
            ) {
                visited[nX][nY] = true;
                queue.push([nX, nY]);
            }
        }
    }

    return visited;
}

3️⃣ 지게차로 컨테이너 꺼내기

이제 구한 외부 공기 정보를 바탕으로, request로 주어진 문자의 컨테이너를 꺼낼 수 있는지 판단해야 합니다.

maps 배열을 순회하며 주어진 문자와 일치하는 컨테이너일 경우, 상/하/좌/우에 외부 공기가 위치한다면 이 컨테이너는 지게차로 제거할 수 있습니다. 그렇지 않다면, 주어진 문자와 일치하더라도 제거할 수 없습니다.

'A'를 제거할 차례라고 한다면, 다음과 같이 외부와 인접한 A는 제거할 수 있지만 그렇지 않은 A는 제거할 수 없는 것이죠.

이처럼 maps 배열을 순회하면서 제거할 수 있는 컨테이너의 좌표를 toRemove라는 배열에 추가하고, 모두 순회한 후 toRemove에 있는 좌표들의 값을 ''로 변경해주면 컨테이너 제거가 완료됩니다.

let outside = getOutside();
let toRemove = [];

for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
        if (maps[i][j] !== alphabet) continue;

        for (let k = 0; k < 4; k++) {
            let [nX, nY] = [i + dx[k], j + dy[k]];

            // 바깥 공기와 맞닿아 있다면 제거
            if (outside[nX][nY]) {
                toRemove.push([i, j]);
                break;
            }
        }
    }
}

for (let [x, y] of toRemove) {
  	maps[x][y] = '';
}

마지막으로 requests 배열의 모든 원소를 탐색한 이후 maps 배열에 남아 있는 컨테이너의 수를 구하면 문제를 해결할 수 있습니다.

🌕 전체 코드

위 모든 과정을 구현한 전체 코드는 다음과 같습니다.

function solution(storage, requests) {
	let [n, m] = [storage.length, storage[0].length];

	// storage를 바깥 공기로 감싸는 maps 배열 생성
	let maps = Array.from({ length: n + 2 }, () => Array(m + 2).fill(''));
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			maps[i + 1][j + 1] = storage[i][j];
		}
	}

	let dx = [-1, 0, 1, 0];
	let dy = [0, -1, 0, 1];

	// 바깥 공기를 true, 내부를 false로 나타내는 배열을 반환하는 함수
	function getOutside() {
		let visited = Array.from({ length: n + 2 }, () => Array(m + 2).fill(false));
		let queue = [[0, 0]];
		visited[0][0] = true;

		while (queue.length) {
			let [cX, cY] = queue.shift();

			for (let i = 0; i < 4; i++) {
				let [nX, nY] = [cX + dx[i], cY + dy[i]];

				if (
					nX >= 0 &&
					nX < n + 2 &&
					nY >= 0 &&
					nY < m + 2 &&
					!visited[nX][nY] &&
					maps[nX][nY] === ''
				) {
					visited[nX][nY] = true;
					queue.push([nX, nY]);
				}
			}
		}

		return visited;
	}

	for (let request of requests) {
		let alphabet = request[0];

		// 크레인을 이용해 모든 목표 컨테이너 제거
		if (request.length === 2) {
			for (let i = 1; i <= n; i++) {
				for (let j = 1; j <= m; j++) {
					if (maps[i][j] === alphabet) maps[i][j] = '';
				}
			}
		}
		// 지게차를 이용해 바깥 공기와 맞닿아 있는 목표 컨테이너만 제거
		else {
			let outside = getOutside();
			let toRemove = [];

			for (let i = 1; i <= n; i++) {
				for (let j = 1; j <= m; j++) {
					if (maps[i][j] !== alphabet) continue;

					for (let k = 0; k < 4; k++) {
						let [nX, nY] = [i + dx[k], j + dy[k]];

						// 바깥 공기와 맞닿아 있다면 제거
						if (outside[nX][nY]) {
							toRemove.push([i, j]);
							break;
						}
					}
				}
			}

			for (let [x, y] of toRemove) {
				maps[x][y] = '';
			}
		}
	}

	let answer = 0;
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= m; j++) {
			if (maps[i][j] !== '') answer += 1;
		}
	}

	return answer;
}

🧪 실행결과

코드를 제출 후 실행해보면 아래와 같이 통과하는 것을 확인할 수 있습니다.

이 코드의 시간 복잡도는

• requests 배열의 길이: 최대 100
  - 크레인을 이용한 제거: $O(n * m)$
  • 지게차를 이용한 제거: BFS 실행의 시간 복잡도 = $O(n * m)$

이므로 최악의 경우 $O(100 * 50 * 50) = O(250,000)$으로 문제 없이 실행이 가능합니다.