[Python] BOJ 7576: 토마토(feat. 3일 걸렸다.)

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

요구사항

• 시간제한 1초
  • O(n**2) 10,000,000 천만번 정도 연산이 최대니깐 괜찮다. 
• 메모리 제한 256MB 넉넉할 거 같다. 
• 며칠이 지나야 토마토들이 모두 익는 지, 최소 일수를 구해라

설계

• BFS 방식으로 풀자. 
• 익은 토마토들을 따로 빼준다. 
  • 방금 든 생각인데 여기서 익은 토마토가 없다면 print(-1) exit() 하는 것도 좋을 거 같다. 
  • 그럴 필요없겠다. while queue에서 걸린다, 그래도 뭐 빨리 발견하니깐 하는 게 좋은건가? 모르겠다. 
• 익은 토마토를 BFS 방식으로 탐색해준다. 
• 2 중 for문을 사용해서 최대값을 구한다. 

구현(사실상 최종 코드는 블로그 맨 아래 참고)

from collections import deque
import sys

input = lambda: sys.stdin.readline().rstrip()

m, n = map(int, input().split())

tomato_box = []
for _ in range(n):
    row = list(map(int, input().split()))  # 각 행을 리스트로 입력받음
    tomato_box.append(row)

queue = deque([])

# 큐에 익은 토마토 좌표를 추가
for i in range(n):
    for j in range(m):
        if tomato_box[i][j] == 1:
            queue.append((i, j))

# 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if tomato_box[nx][ny] == 0:  # 익지 않은 토마토가 있는 경우
                    tomato_box[nx][ny] = tomato_box[x][y] + 1
                    queue.append((nx, ny))

# BFS 수행
bfs()

# 모든 토마토가 익었는지 확인
days = 0
for row in tomato_box:
    for value in row:
        if value == 0:  # 익지 않은 토마토가 남아 있는 경우
            print(-1)
            exit()
        days = max(days, value)

# 걸린 일수 출력 (처음이 1이므로 -1)
print(days - 1)

• 헷갈리만한 부분만 설명해주겠다. 혹시 다른 부분이 헷갈리면 댓글 남겨주면 더 설명해드립니다. 하루 안으로 ! 
• dx, dy는 헷갈리시면 문제를 작게 reduction 하여 돌려보세요. 
• while queue: 하는 이유는 BFS 탐색을 하기 위해서 입니다. 
  • 초기에 queue에는 익은 토마토들의 좌표가 들어갑니다. 
  • 예를 들어 아래와 같이 입력을 한다면 queue = ((2, 2)) 가 초기 상태 입니다. 
  • 3 3 
  • 0 0 0
  • 0 0 0
  • 0 0 1
• if 0 <= nx < n and 0 <= ny < m: 
  • 상 하 좌 우 로 이동했을 때, 토마토 박스의 범위 안에 있는 경우만 if문 아래를 실행합니다.
  • 예를 들어서, 아래와 같은 때 뜬금없이 좌표 (100, 100)도 탐색하면 안되겠죠? 그럴 일 없겠지만
  • 0 0 0
  • 0 0 0
  • 0 0 1 
• for value in row: 
  • 여기서 value는 최소일수가 계속 더해진 형태입니다.
  • 예를 들어
  • 초기 상태
  • 3 3
  • 0 0 0
  • 0 0 0
  • 0 0 1
  • 다음 날
  • 0 0 0
  • 0 0 2
  • 0 2 1
  • 다음 날
  • 0 0 3
  • 0 3 2 
  • 3 2 1
  • 다음 날
  • 0 4 3
  • 4 3 2
  • 3 2 1
  • 다음 날
  • 5 4 3
  • 4 3 2
  • 3 2 1
  • 이제 이해해보세요. 

3일 걸린 이유

• 아무리 코드를 수정하고 디버깅 해 보아도 안되는 것이다. 

[디버깅한 흔적...]

from collections import deque
import time
import sys
input = lambda: sys.stdin.readline().rstrip()

n, m = map(int, input().split())

tomto_box = [list(map(int, input().split())) for _ in range(n)]

# 디버깅을 위한 출력
print("초기 tomato_box 상태:", tomto_box)

queue = deque([])

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

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

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and tomto_box[nx][ny] == 0:
                tomto_box[nx][ny] = tomto_box[x][y] + 1
                queue.append((nx, ny))

# BFS 수행
start_time = time.time()  # BFS 시작 시간
bfs()
end_time = time.time()  # BFS 종료 시간

# 디버깅: BFS 종료 후 상태 출력
print("BFS 종료")
print("BFS 수행 시간:", end_time - start_time, "초")

# 다 익는 데 걸리는 시간
days = 0

for row in tomto_box:
    for value in row:
        print(value, end = '')
    print()
        # if value == 0:
        #     print(-1)
        #     exit()
        # days = max(days, value)

print(days-1)

• 그리고 처음에 하나하나 print() 찍어가면서 왜왜 !!! 왜 !! 지금은 되는 데 !!! 예제만 안되냐고 !!! 
• 결론적으로 행과 열을 헷갈렸다

출처: 백준

• 4행 6열 인줄 알았는 데
• 6행 4열이다. 
• 급 헷갈릴 분들을 위해 설명하자면..

출처: 위키피디아

• 아니 사실 내가 맞다 ㅡ3ㅡ 저 예제 입력만 보면 4행 6열이라고 생각하지 6행 4열 이라고 누가 생각하냐
• 아래 문제 사진을 자세히 보면, 열, 행으로 준다고 한다. 

출처: 백준

처음으로 길게 문제를 가져간 이유
1. 하루에 시간을 제한을 두고 풀기 때문이다.
2. BFS 제대로 이해하고 싶기 때문이다. 

회고
1. 먼저 내 코드를 의심하고, 다음은 내 눈을 의심하자
2. 문제를 잘 읽어보자.
3. 테스트 케이스도 잘 보자.
4. 디버깅 하면서 어디가 문제일지 찾는 것도 재미있다.
5. 처음부터 하나씩 출력해보면서 시작하면 시간은 오래걸릴거 같은 데 실전 대비 연습이니깐 그렇게 해보자.