[홀로 하는 코딩 공부] 토마토 (Python)

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/7569

7569번: 토마토

 

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 3차원 배열을 이용한 BFS 문제이다.

• direct 배열은 토마토가 익을 수 있는 6개의 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)으로 향하기 위해 더해져야 하는 값이 저장된다.
• Counter 함수로 box 배열안에 0의 유무를 파악하여 출력되는 값을 선택한다.(소요되는 날짜 or 0 or -1)
• 익은 토마토의 위치를 파악하는 for문을 통해 익은 토마토가 발견된다면 해당 인덱스를 기준으로 bfs함수를 통해 익도록 영향받은 토마토를 찾는다.

▶ 그래서 아래와 같이 작성하였다. 본 코드를 작성하면서도 for문이 4번이나 사용되기에 시간초과가 나지않을까 하는 생각이 있었고, 역시나 처음에 정답률 퍼센테이지가 늘다가 어느순간 시간초과 나게되었다. 

import sys
from collections import deque, Counter
input = sys.stdin.readline

m, n, h = list(map(int, input().split()))
box = [[] for _ in range(h)]
direct = [[0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1], [1, 0, 0], [-1, 0, 0]]

def bfs(z, x, y, visit):
    changed_num = 0
    que = deque()
    que.append([z, x, y])
    visit[z][x][y] = 1

    while que:
        cz, cx, cy = que.popleft()
        for di in direct:
            nz = cz + di[0]
            nx = cx + di[1]
            ny = cy + di[2]
            if 0 <= nz < h and 0 <= nx < n and 0 <= ny < m:
                if box[nz][nx][ny] == 0 and visit[nz][nx][ny] == 0:
                    box[nz][nx][ny] = 1
                    visit[nz][nx][ny] = 1
                    changed_num += 1
    return changed_num

cur_zero_num = 0
for i in range(h):
    for j in range(n):
        tmp = list(map(int, input().split()))
        box[i].append(tmp)
        cur_zero_num += Counter(tmp)[0]
if cur_zero_num == 0:
    print(0)
else:
    day = 1
    while True:
        ch_num = 0
        visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
        for i in range(h):
            for j in range(n):
                for k in range(m):
                    if box[i][j][k] == 1 and visited[i][j][k] == 0:
                        ch_num += bfs(i, j, k, visited)
        if ch_num == 0:
            print(-1)
            break
        else:
            cur_zero_num = 0
            for i in range(h):
                for j in range(n):
                    cur_zero_num += Counter(box[i][j])[0]
            if cur_zero_num > 0:
                day += 1
            else:
                print(day)
                break

 

 

▶ 우선적으로 시간 초과의 주요 요인이라고 생각되었던 for문을 줄일 수 있는 부분부터 찾아서 줄이려고 하였다. 

• 우선 box 배열 값을 입력 받는 부분에서 익은 토마토가 있는 위치까지 같이 검색하여 que에 해당 인덱스를 넣어준다.
• box 배열 값을 익는데 소요되는 날짜라고 칭하고 그 값을 업데이트 한다. (그러면 위에서 정의한 visited 코드가 필요없어진다.) 그리고 익는데 소요되는 날짜 계산을 bfs 함수 밖에서 계산해주는게 아니라 bfs 함수안에서 계산해준다. bfs 함수안에서 6개의 방향을 통해 토마토를 익게 하는 과정을 거칠 때, 영향을 받아 익는 토마토가 있는 위치에 그 전 위치에 있는 값에서 +1을 해준다. (영향을 받아 익는 토마토는 영향을 준 토마토보다 하루가 더 지났다는 의미를 부여하기 위함이다.)
• 그리고 bfs 함수 안에서 0으로 초기화된 day를 업데이트 해나간다. box 배열 값이 익는데 소요되는 날짜라고 칭하였기에 day는 계산이 완료된 box 배열 값안에서 제일 큰 값을 넣으면된다. 그런데 그 계산을 bfs 내 while문 밖에서 하면 계산량이 늘게된다. 그러므로 box 정보가 업데이트 될 때마다 day도 업데이트 되도록 한다.
• box는 처음에 입력 받을 때 익는 토마토를 1로 입력받지만 소요되는 날짜는 0일이다. 그러므로 정확하게 표현하면 box 배열 값에서 -1을 해준게 익는데 소요되는 날짜인 것이다. 그러므로 box 배열 값에서 -1을 해준 값으로 day를 업데이트 한다.  
• 마지막으로 여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다. 라는 조건을 만족하기 위해서 Counter를 이용하여 box 배열 안에 0이 있을 경우, 익지 않는 토마토가 있다는 의미이기에 익지 않는 토마토의 유무에 따라 위의 조건에 맞는 값을 출력하도록 한다.

import sys
from collections import deque, Counter
input = sys.stdin.readline

m, n, h = list(map(int, input().split()))
box = [[] for _ in range(h)]
direct = [[0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1], [1, 0, 0], [-1, 0, 0]]

que = deque()
for z in range(h):
    for x in range(n):
        tmp = list(map(int, input().split()))
        box[z].append(tmp)
        for y in range(m):
            if box[z][x][y] == 1:
                que.append([z, x, y])
def bfs():
    day = 0
    while que:
        cz, cx, cy = que.popleft()
        for di in direct:
            nz = cz + di[0]
            nx = cx + di[1]
            ny = cy + di[2]
            if 0 <= nz < h and 0 <= nx < n and 0 <= ny < m:
                if box[nz][nx][ny] == 0:
                    que.append([nz, nx, ny])
                    box[nz][nx][ny] = box[cz][cx][cy] + 1
                    if day < box[nz][nx][ny]:
                        day = box[nz][nx][ny] - 1
    return day

res = bfs()

cur_zero_num = 0
for z in range(h):
    for x in range(n):
        cur_zero_num += Counter(box[z][x])[0]
if cur_zero_num > 0:
    print(-1)
else:
    print(res)

 

 

▶ 그동안 2차원 배열을 이용한 bfs 문제에 익숙해져있다보니 3차원 배열을 사용하여 해결하려하니 평소 bfs 문제를 푸는 시간보다 훨씬 많은 시간이 소요되었다. 코드를 작성하면서 for문이 많다면 줄이기 위한 방안도 같이 고려하면서 코드를 작성해야겠다. 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.