[알고리즘] BOJ 7569번 - 토마토(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

4 / 50

 

탐색

4 / 50

 

기초 동적 프로그래밍

5 / 50(NEW!)

 

투포인터

0 / 10

---

문제

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

7569번: 토마토

→ solved.ac 기준 골드 5

→ class 3

---

문제 해결 아이디어

토마토를 보관하는 큰 창고 == graph

며칠이 지나면 토마토가 모두 익는가?에 대한 최소 일수 ⇒ 그래프 탐색

 

익은 토마토는 1, 익지 않은 토마토는 0, 안 들어 있으면 -1

탐색해나가면서 칸마다 며칠인지 더해주고,

마지막에 0이 있는지 확인 후 있으면 -1을 출력(토마토가 모두 익지는 못하는 상황).

없으면 가장 최대값을 출력한다.

 

어떻게 탐색하는가 ? BFS? DFS?

→ 처음에 DFS로 접근하려다가 작렬하게 실패... 

→ 해당 문제는 BFS 문제였음..

 

→ for문으로 graph에 접근하여 익은 토마토일 때 bfs 수행

queue에서 안 익은 토마토일 때 방문해서 경로를 기록한다.

→ 틀렸습니다

if, 그럼 만약 익은 토마토의 위치가 각각 x와 y에 있고, x < y라고 할 때

안 익은 z가 y에 더 가깝다.

이렇게 됐을 경우 먼저 x가 bfs를 수행하고 나서 y가 수행되므로 z가 전혀 반영 X. 실제로는 y가 수행되었을 때 반영되어야 한다.

→ 어떻게 x와 y 각각 수행하고 나서 최단 경로만 넣어두지??

→ 첫 번째 시도: 거리를 비교해서 늘 짧은 거리만 넣어둔다.

이렇게 구현했을 때 시간 초과 발생

→ 두 번째 시도: distance와 visited 도입해서 안 익은 토마토이면서 처음 방문했을 때만 최단 거리 기록

이렇게 구현했을 때 역시나 시간 초과 발생

 

최종 아이디어.txt

처음 Queue에 방문이 필요한 노드(== 처음 익은 토마토)를 넣어두고 BFS를 수행

세 번째 시도: 아에 발상 전환, queue에 방문이 필요한 노드를 넣어두고 bfs를 수행

여기서 첫 방문이 필요한 노드는 결국 익은 토마토들.

익은 토마토들을 Queue에 넣어두고 차례로 빼면서 탐색을 수행하면

현재 Queue에 있는 노드와 가까운 것부터 수행되기 때문에 늘 최단 경로만 담게 된다

---

구현

내 풀이

from collections import deque
import sys

input = sys.stdin.readline

# BFS 메서드 정의
def bfs():
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        x, y, z = queue.popleft()
        # 인접한 원소(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)를 큐에 삽입
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if nx < 0 or nx >= h or ny < 0 or ny >= n or nz < 0 or nz >= m:
                continue

            # 안 익은 토마토이면서 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny][nz] == 0 and not visited[nx][ny][nz]:
              queue.append((nx, ny, nz))
              visited[nx][ny][nz] = True
              graph[nx][ny][nz] = graph[x][y][z] + 1
                
def solution():
    tmp = True
    for i in range(h):
        for j in range(n):
            if 0 in graph[i][j]:
                tmp = False

    if tmp:
        return 0

    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    queue.append((i, j, k))

    bfs()
  
    answer = -1
    for i in range(h):
        for j in range(n):
            if 0 in graph[i][j]:
                return -1
            answer = max(answer, max(graph[i][j]))
    
    return answer - 1

m, n, h = map(int, input().split())
graph = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(h)]
queue = deque()

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

print(solution())

---

메모

• 걸린 시간: 2시간 이상..??
  • 예외는 금방 알아챘는데 시간 초과 안 나는 방법을 몰라서 2시간 이상 소요됨.. 
  • 답 보고 나서 며칠 지난 후 다시 풀었다.
• 같은 이름의 토마토라는 문제가 있음.
  • 3차원 배열과 다르게 얘는 2차원 배열.
  • 문제 풀이 방식은 아마 같을 걸로 예상되나 직접 테스트하기에는 훨씬 덜 부담됨.
  • 이거 먼저 풀 걸......

---

마치며

같은 문제지만 토마토 문제도 복습하는 의미에서 나중에 풀어봐야겠다.

어쨌든 첫트에 못 푼 문제이므로 ㅠㅠ(눈물 좔좔...)