이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 문제 해결을 위한 아이디어를 제공하기 위해서
작성되었습니다.

🍅 2차원 토마토

백준 7576 토마토 : https://www.acmicpc.net/problem/7576

💡 아이디어

• 여러 곳에서 동시에 dfs를 수행해야하는 경우, 큐에 시작점을 미리 넣어놓고 bfs()를 호출한다

🌻 나의 풀이

import numpy as np
from collections import deque
# 가로 M, 세로 N
M, N = map(int, input().split())
dq = deque()

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
zero_cnt = 0
graph = []
visited = [[0]*M for _ in range(N)] # 방문처리용 이차원 배열

# graph와 visited 배열 생성
for i in range(N):
    temp = list(map(int, input().split()))
    graph.append(temp)
    for j in range(M):
        if temp[j] == 1:
            dq.append((i, j))
            visited[i][j] = 1
        elif temp[j] == -1:
            visited[i][j] = -1
        elif temp[j] == 0:
            zero_cnt += 1


def bfs():
    while dq:
        y, x = dq.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= N or nx >= M:
                continue
            if graph[ny][nx] == -1:
                continue
            if visited[ny][nx] != 0:
                continue
            visited[ny][nx] = visited[y][x] + 1
            dq.append((ny, nx))


if zero_cnt == 0:
    print(0)
else:
    bfs()
    flag = False
    max_num = 0
    for i in range(N):
        if flag:
            break
        for j in range(M):
            if visited[i][j] == 0:
                print(-1)
                flag = True
                break
            elif visited[i][j] > max_num:
                max_num = visited[i][j]
    if visited[i][j] != 0 and max_num != 0:
        print(max_num - 1)

✍ 아쉬운 점

• graph와 똑같은 visited 이차원 배열을 만들어서 (걸린 날 수 + 1)을 저장했다. 굳이 visited라는 새로운 배열을 만들지 않고 graph 배열을 이용할 수도 있었을 것 같다.
• 익어야할 토마토가 없는 경우 -> 0
  익지 못하는 토마토가 있을 경우 -> -1
  두 가지 경우를 생각해주는데 zero_cnt와 이중 포문을 사용했다. 이 부분 때문에 코드가 길어졌다. 리턴 값을 bfs() 함수 안에서 정해주면 더 깔끔한 코드가 될 것 같다.

20210423 다시 풀어봄

import numpy as np
from collections import deque
import sys

sys.stdin = open("./input_file.txt", "r")


dq = deque()

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

M, N = map(int, input().split())
graph = []

#그래프 입력받아 그리기

for n in range(N):
    graph.append(list(map(int, input().split())))
    for m in range(M):
        if graph[n][m] == 1:
            dq.append((n, m))
date = 0

def bfs(dq):
    temp = deque()
    while dq:
        y, x = dq.popleft()
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue
            if graph[ny][nx] == -1:
                continue
            if graph[ny][nx] == 0:
                graph[ny][nx] = 1
                temp.append((ny, nx))
    return temp


temp = bfs(dq)
while temp:
    date += 1
    temp = bfs(temp)


for n in range(N):
    for m in range(M):
        if graph[n][m] == 0:
            date = -1
            break
    if date == -1:
        break

print(date)

🧐
과거에는 그래프에 숫자를 찍어주면서 date를 구했는데 이번에는 dq와 temp를 이용해서 date를 구했다.
불팰요했던 visited를 제거했다.

🌼 더 나은 풀이

# 토마토 나은 풀이
from collections import deque

M, N = map(int, input().split())
box = []
q = deque()
for i in range(N):
    box.append(list(map(int, input().split())))

# 처음 익은 토마토 위치 큐에 삽입
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            q.append((i, j))

def bfs(M, N, box):
    day = -1
    # 상 하 좌 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while(q):
        day += 1
        for _ in range(len(q)):
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if box[nx][ny] == 0:
                        box[nx][ny] = 1
                        q.append((nx, ny))
    for row in box:
        if 0 in row:
            return -1
    return day

answer = bfs(M, N, box)
print(answer)

리턴값을 bfs() 함수 안에서 -1 혹은 day로 주어서 안익을 토마토가 있는 경우 바로 -1을 출력하고 익어야할 토마토가 없는 경우 day가 0으로 리턴된다.

🍅 3차원 토마토

💡 아이디어

• 3차원 배열을 만들어야한다.
  graph[높이][세로][가로]로 접근할 수 있다.
• 상,하,좌,우 + 위,아래 까지 6개의 방향을 모두 탐색해주어야한다.

dm = [-1, 1, 0, 0, 0, 0]
dn = [0, 0, -1, 1, 0, 0]
dh = [0, 0, 0, 0, -1, 1]

• 걸리는 일 수를 day로 체크해서 리턴해준다.
• 방문처리를 마친 그래프에 0이 있는 경우 0을 리턴해준다.

• 3차원 graph 만들기

M, N, H = map(int, input().split())
graph = []

for i in range(H):
    temp1 = []
    for j in range(N):
        temp2 = list(map(int, input().split()))
        temp1.append(temp2)
    graph.append(temp1)
print(graph)

🎢 3차원 그래프

• 리스트를 입력 받아서 바로 graph에 넣어주는 것이 아니라 temp라는 임시 리스트에 저장해놓고 검사를 마친 후에 temp를 그래프에 append 해 주었다.
• 한 층에 있는 리스트를 temp1에 모아서 graph에 넣어주었다.

나의 풀이

from collections import deque
#sys.stdin = open("testcase/7569.txt", "r")

# 가로 M, 세로 N, 높이 H
M, N, H = map(int, input().split())
graph = []
dq = deque()

zero_cnt = 0
# 3차원 그래프 만들기
for i in range(H):
    temp1 = []
    for j in range(N):
        temp2 = list(map(int, input().split()))
        for k in range(M):
            if temp2[k] == 1:
                dq.append((i, j, k))
            if temp2[k] == 0:
                zero_cnt += 1
        temp1.append(temp2)
    graph.append(temp1)

day = -1


# bfs
def bfs(day):

    dm = [-1, 1, 0, 0, 0, 0]
    dn = [0, 0, -1, 1, 0, 0]
    dh = [0, 0, 0, 0, -1, 1]
    while dq:
        day += 1
        for _ in range(len(dq)):
            h, n, m = dq.popleft()
            for i in range(6):
                nh = h + dh[i]
                nn = n + dn[i]
                nm = m + dm[i]
                if 0 > nh or nh >= H or 0 > nn or nn >= N or 0 > nm or nm >= M:
                    continue
                if graph[nh][nn][nm] == 0:
                    graph[nh][nn][nm] = graph[h][n][m] + 1
                    dq.append((nh, nn, nm))

    for h in range(H):
        for n in range(N):
            if 0 in graph[h][n]:
                return -1
    return day



answer = bfs(day)
print(answer)

🎪 아쉬운 점
day를 카운트해주는게 까다로웠다.
while문 내부에 dq의 길이 만큼 for문을 돌려서 dq에 추가적으로 들어간 것과 분리를 해 주고 그 사이에 day를 카운트했다.
더 좋은 방법이 있을 것 같다.

🍅 2차원 3차원 토마토 후기

• 2차원에서 3차원으로 바꼈지만 문제를 해결하기 위한 아이디어는 완전히 같았다.
• 오히려 두 문제 모두 day를 효과적으로 카운트할 수 있는 방법을 찾는 것이 까다로웠다.
• 처음에는 visited 배열로 방문처리를 해주었지만 이것은 불필요한 방법이었던 것 같고, 기존의 graph에 방문처리를 해주는 방법이 더 좋은 것 같다.