문제 요약
물류창고에는 n x m개의 컨테이너가 놓여 있고, 각 컨테이너는 알파벳 대문자로 종류가 구분된다.
출고 요청은 두 가지 방식으로 들어온다.
- 요청 문자열의 길이가
1이면 지게차를 사용한다. - 요청 문자열의 길이가
2이면 크레인을 사용한다.
예를 들어 요청이 "A"라면 지게차 요청이고, "BB"라면 크레인 요청이다.
출고 방식
지게차
지게차는 요청된 종류의 컨테이너 중 현재 창고 외부와 연결된 컨테이너만 꺼낼 수 있다.
컨테이너의 4면 중 적어도 한 면이 창고 외부와 연결되어 있으면 접근 가능하다고 본다.
여기서 중요한 점은, 이미 꺼낸 컨테이너의 자리는 빈 공간이 되므로 외부와 연결되는 통로가 될 수 있다는 것이다.
크레인
크레인은 접근 가능 여부와 상관없이 요청된 종류의 모든 컨테이너를 꺼낼 수 있다.
즉, 요청이 "BB"라면 창고 안의 모든 B 컨테이너를 제거한다.
핵심 아이디어
이 문제의 핵심은 지게차 요청을 처리할 때마다 현재 외부와 연결된 빈 공간을 찾는 것이다.
컨테이너가 제거된 위치는 빈 공간이 된다.
이 빈 공간이 창고 바깥과 연결되어 있다면, 그 빈 공간과 맞닿은 컨테이너는 지게차로 접근할 수 있다.
따라서 지게차 요청은 다음 방식으로 처리할 수 있다.
- 창고 바깥을 표현하기 위해 전체 격자에 빈 테두리를 추가한다.
- 테두리의 한 점인
(0, 0)에서 BFS를 시작한다. - 빈 공간만 이동하면서 외부와 연결된 영역을 찾는다.
- BFS 중 요청된 컨테이너를 만나면 제거 후보에 넣는다.
- BFS가 끝난 뒤 제거 후보 컨테이너들을 한 번에 제거한다.
왜 테두리를 추가할까?
원래 창고의 바깥은 배열 범위 밖에 있다.
이를 직접 처리하려면 매번 좌표가 범위를 벗어나는지 검사해야 해서 구현이 번거로워진다.
대신 창고를 빈 공간으로 한 겹 감싸면, 창고 외부를 배열 내부에서 표현할 수 있다.
예를 들어 원래 창고가 다음과 같다면,
ABC
DEF테두리를 추가한 격자는 다음과 같이 생각할 수 있다.
.....
.ABC.
.DEF.
.....이제 (0, 0)에서 BFS를 시작하면 창고 외부와 연결된 빈 공간을 자연스럽게 탐색할 수 있다.
지게차 요청 처리
지게차 요청이 "A"라고 하자.
BFS 중 다음 칸을 확인할 때 경우는 두 가지다.
1. 다음 칸이 빈 공간인 경우
외부와 연결된 빈 공간이므로 계속 BFS로 이동한다.
if board[nx][ny] == ".":
visited[nx][ny] = True
q.append((nx, ny))2. 다음 칸이 요청된 컨테이너인 경우
지금 탐색 중인 위치는 외부와 연결된 빈 공간이다.
따라서 그 빈 공간과 맞닿아 있는 요청 컨테이너는 접근 가능하다.
이 컨테이너는 제거 후보에 넣는다.
elif board[nx][ny] == target:
remove_set.add((nx, ny))주의할 점은, 이 컨테이너를 바로 빈 공간으로 바꾸면 안 된다는 것이다.
같은 요청 안에서는 “출고 요청이 들어온 순간 접근 가능한 컨테이너”만 제거해야 한다.
따라서 제거할 좌표를 먼저 모아두고, BFS가 끝난 뒤 한 번에 제거한다.
크레인 요청 처리
크레인 요청은 간단하다.
요청된 종류의 컨테이너를 전체 격자에서 찾아 모두 제거하면 된다.
for i in range(1, n + 1):
for j in range(1, m + 1):
if board[i][j] == target:
board[i][j] = "."전체 코드
from collections import deque
def solution(storage, requests):
n = len(storage)
m = len(storage[0])
board = [["."] * (m + 2)]
for row in storage:
board.append(["."] + list(row) + ["."])
board.append(["."] * (m + 2))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def use_forklift(target):
visited = [[False] * (m + 2) for _ in range(n + 2)]
q = deque([(0, 0)])
visited[0][0] = True
remove_set = set()
while q:
x, y = q.popleft()
for dx, dy in directions:
nx = x + dx
ny = y + dy
if not (0 <= nx < n + 2 and 0 <= ny < m + 2):
continue
if visited[nx][ny]:
continue
if board[nx][ny] == ".":
visited[nx][ny] = True
q.append((nx, ny))
elif board[nx][ny] == target:
remove_set.add((nx, ny))
for x, y in remove_set:
board[x][y] = "."
def use_crane(target):
for i in range(1, n + 1):
for j in range(1, m + 1):
if board[i][j] == target:
board[i][j] = "."
for request in requests:
target = request[0]
if len(request) == 1:
use_forklift(target)
else:
use_crane(target)
answer = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if board[i][j] != ".":
answer += 1
return answer동작 예시
다음 입력을 보자.
storage = ["AZWQY", "CAABX", "BBDDA", "ACACA"]
requests = ["A", "BB", "A"]첫 번째 요청 "A"는 지게차 요청이다.
현재 외부에서 접근 가능한 A 컨테이너만 제거한다.
두 번째 요청 "BB"는 크레인 요청이다.
접근 가능 여부와 상관없이 모든 B 컨테이너를 제거한다.
세 번째 요청 "A"는 다시 지게차 요청이다.
앞선 요청들로 인해 생긴 빈 공간이 외부와 연결되어 있을 수 있으므로, 다시 BFS로 외부 연결 영역을 계산한 뒤 접근 가능한 A만 제거한다.
최종적으로 남은 컨테이너 수는 11이다.
시간 복잡도
창고의 크기를 n x m, 요청의 개수를 r이라고 하자.
각 요청마다 최대 한 번 전체 격자를 확인한다.
- 지게차 요청: BFS로 전체 격자를 최대 한 번 탐색
- 크레인 요청: 전체 격자를 한 번 순회
따라서 시간 복잡도는 다음과 같다.
O(r * n * m)제한 조건은 다음과 같다.
n, m <= 50
r <= 100최대 연산량은 대략 100 * 50 * 50 = 250,000 정도이므로 충분히 빠르다.
공간 복잡도는 BFS 방문 배열과 격자 저장 공간 때문에 다음과 같다.
O(n * m)정리
이 문제는 단순히 가장자리 컨테이너만 확인하는 문제가 아니다.
이미 제거된 컨테이너의 빈 공간이 외부와 연결되면서 새로운 접근 경로가 생길 수 있다.
따라서 지게차 요청을 처리할 때마다 현재 창고 상태를 기준으로 외부와 연결된 빈 공간을 BFS로 찾아야 한다.
핵심은 다음과 같다.
- 창고 바깥을 표현하기 위해 빈 테두리를 추가한다.
- 지게차 요청은
(0, 0)에서 BFS를 시작해 외부와 연결된 빈 공간을 찾는다. - BFS 중 요청된 컨테이너를 만나면 제거 후보로 저장한다.
- 제거 후보는 BFS가 끝난 뒤 한 번에 제거한다.
- 크레인 요청은 해당 종류의 모든 컨테이너를 제거한다.
이렇게 구현하면 모든 요청을 순서대로 정확하게 처리할 수 있다.
