DDOING

Record my study

My code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        time = 0
        count = 0
        dx = [1,0,-1,0]
        dy = [0,1,0,-1]
        queue = deque()

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    queue.append([i,j])
                elif grid[i][j] == 1:
                    count += 1

        while queue and count > 0:
            time += 1
            for _ in range(len(queue)):
                y,x = queue.popleft()
                for i in range(4):
                    new_x = x + dx[i]
                    new_y = y + dy[i]
                    if (new_x >= 0 and new_x < len(grid[0])) and (new_y >= 0 and new_y < len(grid)):
                        if grid[new_y][new_x] == 1:
                            queue.append([new_y,new_x])
                            grid[new_y][new_x] = 2
                            count -= 1
            
        if count == 0:
            return time
        else:
            return -1


1
2

Runtime : 59ms (beats 61.39)   
Memory : 16.29MB (beats 86.60%)

풀이

  1. grid 내에서 썩은 토마토의 위치를 queue에 추가 + 신선한 토마토 갯수 파악
  2. BFS를 진행하며 dx dy의 위치 변화를 사용하여 상하좌우 위치를 탐색
  3. 만약 도착한 곳의 토마토가 신선한 상태이면 해당 위치의 grid를 2로 바꾸며 신선한 토마토 갯수 - 1
  4. return 시 만약 신선한 토마토의 갯수가 0이면 time을 반환하지만, 남아있다면 -1 반환

BFS는 약간 정형화된 모습이 있기 때문에 먼저 BFS를 구현하고 세부 로직을 생각하였다. dx,dy 배열을 사용하여 상하좌우 위치탐색을 구현하고, grid의 배열 내의 값을 2로 변화시키며 따로 visited를 선언하지 않아 메모리를 아낄 수 있었다.

참고