[모각코] 210721 Today I Learned

<백준 7576번 - 토마토> 

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

 

요새 dfs, bfs를 공부 중이었는데 익숙치 않아서 한 문제 푸는데 2-3일 걸리고 그랬다.

이 문제도 일요일에 처음 풀었는데 못 풀어서 모각코 때 다시 풀어야지. 하고 다른 공부했다.

 

bfs는 그냥도 어려운데 이번 문제는 다른 문제들과 달리 n, m 으로 입력받는 게 아니라 m, n으로 입력 받아서 헷갈렸다.

그거 뭐 얼마나 바뀌었다고 헷갈리냐고 하면.. 할 말이 없다. 저는 코딩 바보예요.

종이에 계속 쓰면서 n이 row고, m이 col이다 라는 걸 계속 상기시켜주었다.

 

1. 

기본 틀은 다른 bfs 문제들이랑 거의 비슷했는데 이 문제에서 좀 특별한? 점은 q.popleft()하기 전에 range(len(q))로 for문을 돌려준 것이다. 익은 토마토 주위에 있는 안 익은 토마토들을 하나하나 다 큐에 넣고 빼고 해주어야 하므로 for문을 사용했다.

첫 코드에서는 이렇게 할 생각을 하지 못해서 예제도 틀렸었다.

 

2. 

그리고 다른 문제 풀 때도 한 번 말했던 건데 다 풀고 나서 예외 경우를 처리해줄 때 자꾸 예외가 아니라 또 하나의 경우로 생각한다. 그래서 조건 찾느라 애를 먹는데, 그게 예외라는 것을 계속해서 인지하고 더 간단한 조건문으로 처리할 수 있게끔 연습해야겠다.

 

3.

첫 코드에서는 q = deque()를 bfs 함수 내부에서 처리했는데 다시 풀 때는 bfs 바깥에서 미리 큐에 1인 값들을 다 넣은 다음 bfs 함수를 돌려서 풀었다.

q = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i, j))

 

 

 

처음 코드가 있었으면 비교하기 수월했을텐데, 아무 생각 없이 그 코드 바로 이용해서 풀어서 전에 틀린 코드를 찾을 수가 없다..

그래도 일단 맞았으니 뿌듯하다!

좀 더 자세한 코드 설명은 또 따로 올려야지.

 

import sys
from collections import deque

def bfs(v_row, v_col):
    count = 0
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        count += 1
        for i in range(len(q)):
            v_row, v_col = q.popleft()
            for row_move, col_move in move:
                row = v_row + row_move #v_row: 이동 전 값. row: 이동 후 값
                col = v_col + col_move
                if 0 <= row < n and 0 <= col < m and tomato[row][col] == 0:
                    tomato[row][col] = 1
                    q.append((row, col))
    
    for i in tomato:
        if 0 in i: #다 익지는 못하는 경우
            return -1
    return count - 1 #처음에는 count 안 하므로 빼줘야 함

m, n = map(int, sys.stdin.readline().split())
tomato = [0 for i in range(n)]
for i in range(n):
    tomato[i] = list(map(int, sys.stdin.readline().split()))

q = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i, j))

print(bfs(n, m))

 

 

2021.07.23 - [Coding/백준] - [Python] 백준 7576번 - 토마토

1번 설명 관련하여 틀린 것이 있어서 위 링크에서 수정하였다.