[백준] 7569 - 토마토

https://www.acmicpc.net/problem/7569

7569번: 토마토

문제 한줄 이해

-상자에 익은 토마토와 익지 않은 토마토가 담겨있고 아무것도 담기지 않은 공간이 있을때 익은 토마트는 하루가 지나면 익지 않은 토마토를 익게 만들때 토마토를 모두 익은 상태로 만들기 위한 날짜 구하기

생각난 풀이

1번째 방법: 먼저 그래프에 익은 토마토를 먼저 큐에 담아주고 BFS를 통해 값 구하기

2차원 그래프로 선언, BFS탐색, 위층 아래층은 현재 위치에서 N만큼 빼주기

import sys
from collections import deque
M, N, H = map(int ,sys.stdin.readline().split())
graph=[]
visited = [[False for i in range(M)] for i in range(N*H)]
cnt = 0

# 그래프를 어떻게 담을까?
for i in range(N*H):
    graph.append(list(map(int, sys.stdin.readline().split())))

# 그래프를 담았어 어떻게 할래? 난 bfs쓸래
def bfs():
    global cnt
    que = deque()
    for i in range(N*H):
        for j in range(M):
            if graph[i][j] == 1:
                
                que.append((i,j))
    while que:
        nowx,nowy = que.popleft()
        visited[nowx][nowy] = True
        dx = [0,0,1,-1,N,-N]
        dy = [1,-1,0,0,0,0]
        
        for i in range(6):
            nextx = nowx + dx[i]
            nexty = nowy + dy[i]
            if nextx>=0 and nexty>=0 and nextx <= N*H-1 and nexty <=M-1:
                if graph[nextx][nexty] == 0 and visited[nextx][nexty] == False:
                    graph[nextx][nexty] = graph[nowx][nowy] + 1
                    que.append((nextx,nexty))
bfs()
ans = 0
for i in range(N*H):
    for j in range(M):
        if graph[i][j] == 0:
            print(-1)
            exit()
        if ans < graph[i][j]:
            ans = graph[i][j]
print(ans-1)

제출 했지만 1퍼만 오르게 대차게 틀렸습니다 .....

이때 반례를 찾아 봤을때 2차원 배열로 담게 되면 상하좌우를 파악할때 

2차원 배열로 선언하게 되면 현재 코드에서 다음 층인데 nextx = 1+nowx에 의해 탐색이 된다.

 

2번째 방법: 3차원 배열로 선언하기

import sys
from collections import deque
M, N, H = map(int ,sys.stdin.readline().split())
graph=[[]for i in range(H)]

# 그래프를 어떻게 담을까?
for i in range(H):
    for j in range(N):
        graph[i].append(list(map(int, sys.stdin.readline().split())))
# 그래프를 담았어 어떻게 할래? 난 bfs쓸래
def bfs():
    que = deque()
    for k in range(H):
        for i in range(N):
            for j in range(M):
                if graph[k][i][j] == 1:
                    que.append((k,i,j))
    while que:
        nowh,nowx,nowy = que.popleft()
        dx = [0,0,1,-1,0,0]
        dy = [1,-1,0,0,0,0]
        dh = [0,0,0,0,1,-1]
        
        for i in range(6):
            nextx = nowx + dx[i]
            nexty = nowy + dy[i]
            nexth = nowh + dh[i]
            if nextx>=0 and nexty>=0 and nexth>=0 and nextx <= N-1 and nexty <=M-1 and nexth<=H-1:
                if graph[nexth][nextx][nexty] == 0 :
                    graph[nexth][nextx][nexty] = graph[nowh][nowx][nowy] + 1
                    que.append((nexth,nextx,nexty))
bfs()
ans = 0
for k in range(H):
    for i in range(N):
        for j in range(M):
            if graph[k][i][j] == 0:
                print(-1)
                exit()
            if ans < graph[k][i][j]:
                ans = graph[k][i][j]
print(ans-1)

3차원 배열이 있는건 알고 있었지만 실제로 쓰게 될줄은 몰랐다 ...