[Programmers/Lv. 2/Python] 지게차와 크레인

📎 문제 정보

난이도	Lv. 2/ 2025 프로그래머스 코드챌린지 1차 예선
유형	BFS, 시뮬레이션, 구현
언어	Python
플랫폼 / 제목	Programmers / 지게차와 크레인

---

🔍 문제 분석

• n×m 창고에 알파벳으로 구분되는 컨테이너가 놓여 있고, 요청이 들어올 때마다 특정 종류를 꺼낸다.
• 요청 문자열 길이가 1이면 지게차 출고, 길이가 2면 크레인 출고

---

💡 풀이 아이디어

• memo로 제거된 칸을 표시하고, 크레인 요청은 storage[y][x] == delete_w인 칸을 위치 상관없이 바로 제거한다.
• 지게차 요청 직전마다 get_border()로 BFS를 새로 돌려서 외부와 연결된 칸을 구한다.
• is_border(board, y, x)로 해당 칸이 격자 테두리 자체이거나, 이웃 중 하나라도 외부와 이어진 칸이라면 접근 가능한 것으로 판정 후 제거한다.

---

💻 코드

from collections import deque


def solution(storage, requests):
    n, m = len(storage), len(storage[0])
    memo = [[0] * m for _ in range(n)]

    answer = n * m
	
    # 빈 칸들 중에서 어디가 외부와 진짜로 뚫려있는지 표시하기
    def get_border():
        visited = [[0] * m for _ in range(n)]
        q = deque()

        for y in range(n):
            for x in range(m):
                if (y == 0 or x == 0 or y == n - 1 or x == m - 1) and memo[y][x] == 1:
                    visited[y][x] = 1
                    q.append((y, x))

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

            while q:
                cy, cx = q.popleft()
                for i in range(4):
                    ny, nx = dy[i] + cy, dx[i] + cx
                    if ny < 0 or nx < 0 or ny >= n or nx >= m: continue
                    if memo[ny][nx] != 1: continue
                    if visited[ny][nx] == 1: continue

                    visited[ny][nx] = 1
                    q.append((ny, nx))

        return visited
	
    # 컨테이너가 있는 칸을 지게차로 꺼낼 수 있는지 판단하기
    def is_border(board, y, x):
        if y == 0 or x == 0 or y == n - 1 or x == m - 1:
            return True

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

        for i in range(4):
            ny, nx = dy[i] + y, dx[i] + x
            if board[ny][nx] == 1:
                return True

        return False

    for request in requests:
        if len(request) == 2:
            delete_w = request[0]
            for y in range(n):
                for x in range(m):
                    if memo[y][x] == 1: continue
                    if storage[y][x] == delete_w:
                        memo[y][x] = 1
                        answer -= 1

        else:
            board = get_border()
            for y in range(n):
                for x in range(m):
                    if board[y][x] == 1: continue
                    if not is_border(board, y, x): continue
                    if storage[y][x] == request:
                        memo[y][x] = 1
                        answer -= 1

    return answer

 

---

⏱️ 시간/공간 복잡도

시간 복잡도	O(R × n × m) - 요청 R개마다 지게차면 BFS
공간 복잡도	O(n × m)

---

📝 배운 점 / 실수했던 부분

• BFS에서는 큐를 활용할 것!!!
• 처음에는 이웃 칸이 비어있는지만 보고 접근 가능 여부를 판단했는데, 그 빈 칸 자체가 외부와 단절된 고립 공간일 수 있어 오답이었음..