[백준] 7576번 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1

8

예제 입력 2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2

-1

예제 입력 3

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력 3

6

예제 입력 4

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력 4

14

예제 입력 5

2 2
1 -1
-1 1

예제 출력 5

0

내 코드

import sys
from collections import deque

input = sys.stdin.readline

# 상하좌우 변수 설정
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def bfs(now_box, input_q):
    queue = deque(input_q)
    next_queue = []

    while queue:
        x, y = queue.popleft()
        now_box[y][x] = -1  # 방문처리

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and now_box[ny][nx] == 0:
                now_box[ny][nx] = 1
                next_queue.append((nx, ny))

    return now_box, next_queue

# 값 받기
M, N = map(int, input().split())
now_box = [list(map(int, input().split())) for _ in range(N)]

during_day = 0
queue = deque([])

# 첫 위치 찾기
for y in range(N):
    for x in range(M):
        # 현 위치가 토마토면
        if now_box[y][x] == 1:
            queue.append((x, y))

# 첫 위치 찾은 후 반복
while True:
    now_box, queue = bfs(now_box, queue)

    if len(queue) == 0:
        sum_of_0 = sum([row.count(0) for row in now_box])
        if sum_of_0 == 0:
            break
        during_day = -1
        break

    during_day += 1

print(during_day)

chatGPT

수정된 코드

import sys
from collections import deque

input = sys.stdin.readline

# 상하좌우 방향 설정
DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def bfs(box, ripe_tomatoes):
    queue = deque(ripe_tomatoes)
    next_day_queue = []

    while queue:
        x, y = queue.popleft()

        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and box[ny][nx] == 0:
                box[ny][nx] = 1  # 익히기
                next_day_queue.append((nx, ny))

    return box, next_day_queue

# 입력 받기
M, N = map(int, input().split())  # 가로 칸 수(M), 세로 칸 수(N)
box = [list(map(int, input().split())) for _ in range(N)]

days = 0
ripe_tomatoes = deque([])

# 초기 익은 토마토 위치 찾기
for y in range(N):
    for x in range(M):
        if box[y][x] == 1:
            ripe_tomatoes.append((x, y))

# BFS를 통해 토마토 익히기
while True:
    box, ripe_tomatoes = bfs(box, ripe_tomatoes)

    if not ripe_tomatoes:  # 다음날 익을 토마토가 없는 경우
        unripe_count = sum(row.count(0) for row in box)
        if unripe_count == 0:
            break  # 모든 토마토 익음
        days = -1
        break  # 익지 못하는 토마토 존재

    days += 1

print(days)

1. 가독성 향상

• 변수 이름 통일 및 명확화:
  • 개선된 코드에서는 directions를 대문자 형태의 상수인 DIRECTIONS로 정의해, 변경되지 않는 값임을 명확히 했습니다. 이는 코드를 읽는 사람에게 해당 값이 고정임을 직관적으로 전달합니다.
  • queue와 next_queue라는 변수명이 queue와 next_day_queue로 변경되어 더 의미를 명확히 했습니다. next_day_queue라는 이름은 다음날 익힐 토마토를 저장하는 목적을 명확히 보여줍니다.

---

2. 불필요한 방문 처리 제거

• box[y]= -1 제거:
  • 원래 코드에서는 BFS 탐색 중 box[y]= -1로 방문 처리를 했지만, 이는 익은 토마토를 1로 처리하는 로직과 중복될 가능성이 있었습니다. 개선된 코드에서는 이 부분이 제거되었고, 익은 토마토는 항상 1로 처리되므로 불필요한 방문 처리가 없어졌습니다.
  • 이는 메모리 사용량을 줄이고 코드의 복잡성을 낮춥니다.

---

3. 불필요한 반복 제거

• 개선된 코드에서는 bfs 함수 내에서 queue만을 사용하며, 새로운 익은 토마토를 next_day_queue로 처리합니다.
• while 루프 종료 후 ripe_tomatoes가 비어 있는지 확인하는 부분도 간결하게 구성했습니다.

---

4. 종료 조건 간결화

• 개선된 코드에서는 종료 조건을 if not ripe_tomatoes와 sum(row.count(0) for row in box)로 명확히 분리해 처리했습니다. 이로 인해 모든 토마토가 익은 상태와 익지 못하는 상태를 명확히 구분했습니다.
• 원래 코드에서 sum_of_0 변수를 추가로 생성했지만, 개선된 코드에서는 불필요한 변수 생성 없이 한 번의 sum으로 처리해 간결성을 높였습니다.

---

5. 코드 흐름 최적화

• days 증가 로직을 반복 루프 내에서 처리하므로, 루프를 돌 때마다 명확히 일수를 추적합니다.
• BFS 내부에서 box[ny][nx] = 1을 처리하고 다음 날 익힐 토마토를 별도의 큐에 담는 방식으로, 방문 및 갱신 과정을 한 번에 처리합니다.

---

코드 정리 요약

개선 사항 기존 코드 개선된 코드

변수명	directions, queue, next_queue	DIRECTIONS, queue, next_day_queue
방문 처리 방식	box[y][x] = -1 사용	제거하고 box[ny][nx] = 1로만 처리
종료 조건 확인	sum_of_0로 익지 않은 토마토 갯수 확인	한 번의 sum으로 모든 조건 처리
큐 처리 방식	익은 토마토 위치와 새로운 큐를 반복적으로 갱신	next_day_queue로 BFS 탐색 분리
가독성	변수 및 종료 조건이 혼재	가독성 높이고 루프 흐름을 단순화

부가 질문

내 생각

1. 상수의 변수명을 대문자로 하자.
2. 방문 처리가 꼭 필요한지 확인하고, 불필요하면 없애자.
3. 비어있는 리스트 확인 문법을 잘 쓰자. if not ripe_tomatoes: