토마토

7576번: 토마토

🤔생각해보기

지금까지 시작 지점이 하나인 그래프 탐색은 비교적 간단하게 해결할 수 있었다.

하지만 이 문제는 동시에 여러 지점에서 탐색을 진행해야해서 어떻게 해야할까 고민이였는데, 잘 생각해보니 그냥 BFS 알고리즘에다가 시작지점만 여러개를 넣어주면 되는 것이였다.

1. 익은 토마토의 좌표를 찾아서 root 배열에 담아놓는다.
2. BFS 탐색을 위해 queue 에 root 들을 담은 상태로 초기화한다.
3. 미로 탐색 과정을 응용해서 전 칸의 값에 1을 증가시킨 값을 다음 칸에 할당한다.
4. 탐색이 종료된 시점의 칸에 담긴 값에서 -1 을 해준 값을 리턴한다. 숫자가 1에서부터 시작하기 때문이다.
5. 전체 박스를 검사해서 토마토가 익지 않은 칸이 있다면 -1 을 리턴해준다.

성공 코드

from collections import deque

M, N = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(N)]

visited = [[0] * M for _ in range(N)]


def bfs():
    day = 0
    queue = deque(root)
    while queue:
        y, x = queue.popleft()

        visited[y][x] = 1

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if visited[ny][nx] == 0 and box[ny][nx] == 0:
                    box[ny][nx] = box[y][x] + 1
                    queue.append([ny, nx])
                    day = box[ny][nx] - 1

                    # 박스 상태 확인 코드
                    # print('-----')
                    # print(f'{box[ny][nx] - 1}일')
                    # for i in box:
                    #     print(i)

    # 익지 않은 토마토가 있는지 검사하기
    for i in box:
        if 0 in i:
            day = -1

    return day


root = []

for n in range(len(box)):
    for m in range(len(box[n])):
        if box[n][m] == 1:
            root.append([n, m])

print(bfs())

 

- 비슷한 문제로 3차원 응용이 있는데 원리는 같으므로 설명은 생략합니다.

 

7569번: 토마토

from collections import deque

M, N, H = map(int, input().split())
box = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]

visited = [[[0] * M for _ in range(N)] for _ in range(H)]


def bfs():
    day = 0
    queue = deque(root)
    while queue:
        z, y, x = queue.popleft()

        visited[z][y][x] = 1

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

        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H:
                if visited[nz][ny][nx] == 0 and box[nz][ny][nx] == 0:
                    box[nz][ny][nx] = box[z][y][x] + 1
                    queue.append([nz, ny, nx])
                    day = box[nz][ny][nx] - 1

    # 익지 않은 토마토가 있는지 검사하기
    for i in box:
        for j in i:
            if 0 in j:
                day = -1

    return day


root = []

for h in range(len(box)):
    for n in range(len(box[h])):
        for m in range(len(box[h][n])):
            if box[h][n][m] == 1:
                root.append([h, n, m])

print(bfs())

 

 

> 2차원 그래프 탐색 로그

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

-----
1일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 1]
-----
1일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 1]
-----
2일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 3, 2, 1]
-----
2일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]
-----
2일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 0, 3, 2, 1]
-----
3일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 3, 2]
[0, 0, 4, 3, 2, 1]
-----
3일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]
-----
3일
[0, -1, 0, 0, 0, 0]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]
-----
3일
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 0, 4, 3, 2, 1]
-----
4일
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 0, 4, 3, 2]
[0, 5, 4, 3, 2, 1]
-----
4일
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 0, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]
-----
4일
[0, -1, 0, 0, 0, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]
-----
4일
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[0, 5, 4, 3, 2, 1]
-----
5일
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 0, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-----
5일
[0, -1, 0, 0, 5, 4]
[-1, 0, 0, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-----
5일
[0, -1, 0, 0, 5, 4]
[-1, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-----
5일
[0, -1, 0, 6, 5, 4]
[-1, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-----
6일
[0, -1, 0, 6, 5, 4]
[-1, 0, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-----
6일
[0, -1, 0, 6, 5, 4]
[-1, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-----
6일
[0, -1, 7, 6, 5, 4]
[-1, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]

result = -1