백준 7576 : 토마토 (파이썬)

BFS로 풀 수 있는 문제이다.

BFS의 queue에 집어넣고 빼면서 탐색하는 방식을 잘 이해하고 있다면 어렵지 않게 풀었을 것이다.

이 문제와 다른 기초 문제들간의 차별점은 예제 3번과 같이 시작점이 두 개가 되는 경우도 고려해야 한다는 점이다.

이 경우 시작이 되는 Queue 에 두 점의 좌표를 같이 넣어주면 양 방향에서 동시에 탐색을 시작한다.

 

그 외의 조건들은 단순히 반복문을 돌려서 검출해내도 되기 때문에 그다지 어려운 점은 아닌 것 같다.

---

import sys
from collections import deque
M, N = map(int, sys.stdin.readline().split())
def bfs(box, start):
    mx = 0
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    queue = deque()
    queue += start
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if box[nx][ny] == 0:
                box[nx][ny] += box[x][y] + 1
                if box[nx][ny] > mx:
                    mx = box[nx][ny]
                queue.append((nx, ny))
    for j in box:
        if 0 in j:
            return -1
    return mx - 1
def box_search(n, m):
    box = []
    start = []
    execution = False
    for _ in range(n):
        box.append([*map(int, sys.stdin.readline().split())])
    for i in range(n):
        for j in range(m):
            if box[i][j] == 0:
                execution = True
            if box[i][j] == 1:
                start.append((i, j))
    if not execution:
        return 0
    else:
        return (box, start)
res = box_search(N, M)
print(bfs(*res) if res else res)

 

 

함수를 쓰지 않고 밖으로 몽땅 꺼내서 반복문을 실행해도 되었겠지만 함수를 쓰는 것이 더 좋아서 그냥 썼다.

함수를 쓰는것에 약간 어색했기 때문에 앞으로 되도록이면 문제들을 함수로 풀어 나갈 예정이다.

---

가끔 백준 코드 길이를 보면 짧게 풀릴 수 있는 문제인데도 엄청 길게 해서 푼 사람들이 있다.

백이면 백 클래스로 푼 사람들이다.

나도 다양한 방식으로 문제들을 풀면서 클래스의 사용법에도 좀 더 익숙해져야 하겠다.