백준 7576 토마토

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

7576번: 토마토

📌 해결순서

1. 탐색을 시작하기전에 먼저 0일째에 이미 익은 토마토의 좌표를 que에 추가한다

2. 그 다음에, day를 +1 해주는 기준을 어떻게 잡을지 정말 많은 고민을 했는데

ex)

0일째에 익은 토마토의 갯수가 2라면 len(que) = 2

cnt = 0 으로 시작

1개의 토마토에 의해서 익은 토마토의 갯수가 3이면 que에는 추가로 3개의 좌표가 저장 cnt += 1 해줌

2개의 토마토에 의해서 익은 토마토의 갯수가 2이면 qye에 추가로 2개의 좌표가 저장 cnt +=1 해줌

이 때, cnt == len(que) 이기 때문에 day += 1을 해준다

다음날에는 len(que)가 5이기 때문에 5개의 모든 토마토들에 의해 다른 토마토들이 모두 영향을 받고나서 day +=1 을 해준다

3. que가 비어서 더이상 탐색을 진행할 수 없으면 day -1 return -> 모든 토마토가 익은 날에도 cnt == len(que) 면 day +=1 을 해주기 때문에 하루를 빼줘야함

4. 농장에 안익은 토마토가 있으면 return -1 

 

📌 코드

from collections import deque
import sys

m, n = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


def bfs_my(que):
    day = 0
    size = len(que)
    cnt = 0
    while que:
        x, y = que.popleft()

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

            if((0 <= nx < n) and (0 <= ny < m)):
                if(graph[nx][ny] == 0):
                    graph[nx][ny] = 1
                    que.append((nx, ny))
        cnt += 1

        if(cnt == size):
            day += 1
            size += len(que)

    return day - 1


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

day_que = deque()

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

success = 1

for i in range(n):
    for j in range(m):
        if(graph[i][j] == 0):
            success = 0
            break

if(success):
    print(bfs_my(day_que))
else:
    print(-1)

다 풀고나서 여러 풀이를 참고하고자 여기저기 돌아다니다가 굉장히 좋은 풀이를 발견해서 기록해둔다

익은 토마토의 좌표를 que에 추가하고 탐색을 시작하는것은 동일하지만, 안익은 토마토의 갯수를 추가로 센다

모든 탐색이 끝난후, 안익은 토마토의 갯수가 남아있다면 return -1

 

📌 코드

from collections import deque
import sys

def bfs():
    m, n = map(int, sys.stdin.readline().split())
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    tmt_cnt = 0
    tmt = deque()

    day = 0

    for i in range(n):
        for j in range(m):
            if(graph[i][j] == 0):
                tmt_cnt += 1
            elif(graph[i][j] == 1):
                tmt.append((i, j))

    while tmt and tmt_cnt:
        for _ in range(len(tmt)):
            x, y = tmt.popleft()

            if x > 0 and graph[x - 1][y] == 0:
                graph[x - 1][y] = 1
                tmt.append((x - 1, y))
                tmt_cnt -= 1
            if x < n - 1 and graph[x + 1][y] == 0:
                graph[x + 1][y] = 1
                tmt.append((x + 1, y))
                tmt_cnt -= 1
            if y > 0 and graph[x][y - 1] == 0:
                graph[x][y - 1] = 1
                tmt.append((x, y - 1))
                tmt_cnt -= 1
            if y < m - 1 and graph[x][y + 1] == 0:
                graph[x][y + 1] = 1
                tmt.append((x, y + 1))
                tmt_cnt -= 1
        day += 1

    if tmt_cnt:
        print(-1)
    else:
        print(day)


if __name__ == '__main__':
    bfs()