Leetcode 3568. Minimum Moves to Clean the Classroom

문제

You are given an m x n grid classroom where a student volunteer is tasked with cleaning up litter scattered around the room. Each cell in the grid is one of the following:

'S': Starting position of the student
'L': Litter that must be collected (once collected, the cell becomes empty)
'R': Reset area that restores the student's energy to full capacity, regardless of their current energy level (can be used multiple times)
'X': Obstacle the student cannot pass through
'.': Empty space
You are also given an integer energy, representing the student's maximum energy capacity. The student starts with this energy from the starting position 'S'.

Each move to an adjacent cell (up, down, left, or right) costs 1 unit of energy. If the energy reaches 0, the student can only continue if they are on a reset area 'R', which resets the energy to its maximum capacity energy.

Return the minimum number of moves required to collect all litter items, or -1 if it's impossible.

m x n 크기의 격자 형태 교실이 주어집니다. 한 학생 자원봉사자가 교실 곳곳에 흩어진 쓰레기를 모두 치우려고 합니다.

격자의 각 칸은 다음 문자 중 하나로 표현됩니다.

• 'S': 학생의 시작 위치

• 'L': 반드시 수거해야 하는 쓰레기

  • 한 번 수거하면 해당 칸은 빈 칸이 됩니다.

• 'R': 학생의 에너지를 현재 남은 양과 관계없이 최대치로 완전히 회복시키는 충전 구역

  • 여러 번 이용할 수 있습니다.

• 'X': 학생이 지나갈 수 없는 장애물

• '.': 빈 칸

또한 정수 energy가 주어지며, 이는 학생이 가질 수 있는 최대 에너지량을 의미합니다.

학생은 시작 위치 'S'에서 energy만큼의 에너지를 가진 상태로 출발합니다.

학생이 인접한 칸(위, 아래, 왼쪽, 오른쪽)으로 한 칸 이동할 때마다 에너지가 1만큼 소모됩니다.

에너지가 0이 되면 더 이상 이동할 수 없습니다. 단, 현재 위치가 충전 구역 'R'이라면 에너지가 최대치인 energy까지 다시 회복되므로 계속 이동할 수 있습니다.

모든 쓰레기를 수거하는 데 필요한 최소 이동 횟수를 반환하세요.

모든 쓰레기를 수거하는 것이 불가능하다면 -1을 반환하세요.

---

예시

입력: classroom = ["LS", "RL"], energy = 4

출력: 3

설명:

• 학생은 (0, 1) 칸에서 에너지 4를 가진 상태로 시작합니다.

• 모든 쓰레기를 수거할 수 있는 이동 경로 중 하나는 다음과 같습니다.

  • 이동 1: (0, 1) → (0, 0)으로 이동하여 첫 번째 쓰레기 'L'을 수거합니다.
    에너지 1을 사용하여 3이 남습니다.
  • 이동 2: (0, 0) → (1, 0)의 'R' 칸으로 이동합니다.
    이곳에서 에너지가 다시 최대치인 4로 회복됩니다.
  • 이동 3: (1, 0) → (1, 1)로 이동하여 두 번째 쓰레기 'L'을 수거합니다.

• 학생은 총 3번 이동하여 모든 쓰레기를 수거할 수 있습니다.

따라서 출력은 3입니다.

---

제한

• $1 \le m = \texttt{classroom.length} \le 20$
• $1 \le n = \texttt{classroom[i].length} \le 20$
• classroom[i][j]는 'S', 'L', 'R', 'X', '.' 중 하나입니다.
• $1 \le \texttt{energy} \le 50$
• 격자에는 'S'가 정확히 하나 존재합니다.
• 격자에는 'L' 칸이 최대 10개 존재합니다.

---

풀이

해당 문제에서 가장 중요한 부분은 현재까지 어떤 쓰레기를 수거했는지를 효율적으로 상태화하는 것이다.

이를 위해 먼저 격자 전체를 순회하며 쓰레기 'L'의 위치를 확인한다. 이후 원래 격자와 동일한 크기의 2차원 배열 litter를 만들고, 각 쓰레기가 있는 위치에

• 1 << (현재까지 찾은 쓰레기의 개수)

를 저장한다.

즉, 각각의 쓰레기에 서로 다른 하나의 비트를 식별자로 부여하는 것이다.

예를 들어 쓰레기가 3개라면 각각 다음과 같은 값을 가진다.

• 첫 번째 쓰레기: 001
• 두 번째 쓰레기: 010
• 세 번째 쓰레기: 100

이후 특정 칸의 쓰레기를 수거할 때 현재 마스크와 OR 연산을 수행하면,

new_litter_mask = m | litter[dr][dc]

현재까지 수거한 쓰레기의 상태를 하나의 정수로 관리할 수 있다.

모든 쓰레기를 수거한 상태는

(1 << litter_count) - 1

이 된다. 모든 쓰레기에 해당하는 비트가 1인 상태이므로, 현재 마스크가 이 값과 같은지만 확인하면 모든 쓰레기를 수거했는지 쉽게 판단할 수 있다.

또 하나 중요한 점은 같은 위치에 같은 쓰레기 수거 상태로 도착했을 때, 가장 많은 에너지가 남아 있는 경우만 유지하는 것이다.

best_energy[r][c][mask]에는 (r, c) 위치에 mask만큼의 쓰레기를 수거한 상태로 도착했을 때의 최대 잔여 에너지를 저장한다.

만약 이미 동일한 (위치, 쓰레기 상태)에 더 많은 에너지를 가진 채 도착한 적이 있다면, 현재 상태에서는 이후에 만들 수 있는 경로가 기존 상태보다 유리할 수 없다. 따라서 해당 상태를 다시 탐색할 필요가 없다.

반대로 현재 경로가 더 많은 에너지를 가지고 있다면 이후 더 멀리 이동할 가능성이 있으므로 큐에 추가한다.

이렇게 하면 BFS를 사용하면서도 불필요하게 동일한 상태를 반복해서 탐색하는 것을 방지할 수 있다.

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        ROW = len(classroom)
        COL = len(classroom[0])
        DIRS = [
            [0, 1],
            [0, -1],
            [1, 0],
            [-1, 0]
        ]

        start = (-1, -1)
        litter = [[0] * COL for _ in range(ROW)]

        litter_count = 0
        for r, row in enumerate(classroom):
            pos = row.find('S')
            if pos >= 0:
                start = (r, pos)

            for c in range(COL):
                if classroom[r][c] == 'L':
                    litter[r][c] = 1 << litter_count
                    litter_count += 1

        full = 1 << litter_count

        best_energy = [
            [defaultdict(lambda: -1) for _ in range(COL)]
            for _ in range(ROW)
        ]

        def bound(row: int, col: int) -> bool:
            return (
                0 <= row < ROW
                and 0 <= col < COL
                and classroom[row][col] != 'X'
            )

        # row, col, litter mask, turn, energy
        q = deque([(*start, 0, 0, energy)])

        while q:
            r, c, m, t, e = q.popleft()

            if m == full - 1:
                return t

            if e == 0:
                continue

            for tr, tc in DIRS:
                dr, dc = r + tr, c + tc

                if not bound(dr, dc):
                    continue

                new_litter_mask = m | litter[dr][dc]
                new_energy = (
                    energy
                    if classroom[dr][dc] == 'R'
                    else e - 1
                )

                if best_energy[dr][dc][new_litter_mask] < new_energy:
                    best_energy[dr][dc][new_litter_mask] = new_energy
                    q.append(
                        (dr, dc, new_litter_mask, t + 1, new_energy)
                    )

        return -1