예외를 찾아내는 능력 (#7569 토마토)

#7569 토마토 (https://www.acmicpc.net/problem/7569)

 

오랜만에 풀어낸 BFS문제였다.

 

from sys import stdin
from collections import deque

input = stdin.readline
# 쌓아올려지는 상자의 수를 나타내는 H
# M은 상자의 가로 칸의 수
# N은 상자의 세로 칸의 수를 나타낸다
# 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다
m, n, h = map(int, input().split())


tomato = []  # 토마토 상자 데이터
red = deque()  # 익은 토마토 데이터

# 방문 기록
visited = [[[-1 for _ in range(m)] for __ in range(n)] for ___ in range(h)]
# 방문은 0, 미방문은 -1 --> **조건 체크 할 때 유의할 것**
# 따라서, 모든 노드를 방문할 수 없을 경우, sum(visitied)이 음수가 나오게 한다.

for i in range(h):
    layer = []
    for j in range(n):
        row = input().split()
        for k in range(m):
            item = int(row[k])
            # 정수 1은 익은 토마토
            # 정수 0 은 익지 않은 토마토
            # 정수 -1은 토마토가 들어있지 않은 칸
            if item == 1:
                red.append([i, j, k])
                visited[i][j][k] = 0
            elif item == -1:
                visited[i][j][k] = 0
            row[k] = item
        layer.append(row)
    tomato.append(layer)


def is_valid(z, y, x):
    return (0 <= z < h) and (0 <= y < n) and (0 <= x < m) and (tomato[z][y][x] == 0)


# print("visited")
# for i in range(h):
#     for j in range(n):
#         print(visited[i][j])
# print("tomato")
# for i in range(h):
#     for j in range(n):
#         print(tomato[i][j])
# print("after")
answer = 0
# 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력한다.

result_sum = sum([sum([sum(r) for r in l]) for l in visited])
if result_sum == 0:
    print(answer)
else:
    # 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.
    moves = [[-1, 0, 0], [1, 0, 0], [0, 0, -1], [0, 0, 1], [0, -1, 0], [0, 1, 0]]
    next_red = []
    while red:
        ph, py, px = red.popleft()
        for mh, my, mx in moves:
            nh, ny, nx = ph + mh, py + my, px + mx
            if is_valid(nh, ny, nx) and visited[nh][ny][nx] == -1:
                tomato[nh][ny][nx] = 1
                next_red.append([nh, ny, nx])
                visited[nh][ny][nx] = 0

        if len(red) == 0 and len(next_red) > 0:
            red = deque([x for x in next_red])
            next_red = deque()
            answer += 1

    # print("visited")
    # for i in range(h):
    #     for j in range(n):
    #         print(visited[i][j])
    # print("tomato")
    # for i in range(h):
    #     for j in range(n):
    #         print(tomato[i][j])
    # 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
    result_sum = sum([sum([sum(r) for r in l]) for l in visited])
    # print(result_sum)
    if result_sum < 0:
        print(-1)
    else:
        print(answer)

 

 

난 이런 유형의 문제를 "지도 문제" 라고 분류하는 편이다.

이런 문제를 풀이할 때에는 다음 몇 가지 구현이 필요하다.

 

1. visited 리스트

 이걸 plag라고 하는 분들도 계시는 것 같다. 역할은, 해당 노드? postion? index? 암튼 거기에 방문 했는지를 기록하는 것이다. 이걸 기록하지 않으면 방문한 노드에 다시 방문하게 되고, 코드는 무한반복하게 된다. 꼭 필요하다.

2. moves리스트와 is_valid 함수

 moves 리스트는 이동 가능한 방향을 저장한다. 이 문제는 3차원 리스트였어서, 앞 뒤 좌 우 위 아래 총 6개의 경우의 수가 존재했다. 그리고 이렇게 이동한 position이 map의 범위를 벗어나지 않는지 체크하는 is_valid리스트가 필수적이다. 이걸 적용하지 않으면 index가 음수가 나오거나.. 최대 길이를 벗어나는 경우가 생겨 오류가 발생할 수 있다.

 

위 두 가지를 꼭 기억하자.

 

 

 

잘 풀어낸 뒤에 제출을 했는데, 시간초과가 났다.

sys.stdin.readline 적용하고.. 뭐하고 하다보니 시간초과는 해결됐는데

 

92%정도에서 오답이 나왔다.

 

문제에서 요구하는 모든 예외 상황을 잘 처리했음에도 오답이 나오자 질문게시판을 뒤졌다.

다음과 같은 예외를 발견했다.

 

문제에서 제공하는 테스트케이스에는 없는 입력이다.

예외 조건만 보고 저런 테스트케이스를 생각해내시는 분들이 참 대단하다는 생각이 든다.

 

이런걸 잘해야 정말 코테를 잘 풀 수 있는 것 같다.