[DFS/BFS] 백준 7576 토마토

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

7576번: 토마토

 

 

문제)

 

 

 

해설)

이 문제는 당연히 bfs로 풀어야지!! 하면서 좀 헤맸다..ㅎㅎ

두 가지 방식으로 했는데, 코드는 두 번째가 조금 더 깔끔한 것 같다.

 

 

 

풀이 1)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    count = 0
    while tomato:
        second = []
        t_li = tomato.popleft()
        for t_mem in t_li:
            x, y = t_mem[0], t_mem[1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if box[nx][ny] == 0:
                        second.append([nx, ny])
                        box[nx][ny] = 1
                    else:
                        continue
        if second != []:
            tomato.append(second)
        count += 1
    return count - 1

m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

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


day = bfs(tomato)
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            print(-1)
            exit(0)
print(day)

bfs 함수 내에서 며칠이나 걸렸는지 반환해주려고 이 코드를 짜게 되었다.

한 박스에 토마토가 여러 개일 경우 동시에 토마토가 있는 좌표의 옆 토마토들이 익는다.

따라서 하루 단위로 익을 토마토(box에서 0인 애들) list(first, second)를 만들어 저장하고, 그것을 tomato라는 queue에 저장하는 방식으로 구현했다.

 

tomato에서 하나를 뽑으면 그 list에 해당하는 좌표를 순회하고, 해당 list에 저장된 좌표를 모두 돌면 하루가 늘어나는 방식이다.

하지만 여기에는 처음에 토마토가 있던 위치도 하루가 지난 것으로 치는 방식이기에 1을 뺀 값을 반환한다.

 

bfs가 모두 끝나면 혹시 토마토가 익지 않은 경우가 있을 수 있기 때문에 확인해준다.

여기에서 익지 않은 토마토가 있을 경우 -1을 출력하고 exit 하여 끝낸다.

그렇지 않다면 bfs 결과를 출력해준다.

 

 

 

풀이 2)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    while tomato:
        x, y = tomato.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if box[nx][ny] == 0:
                    tomato.append([nx, ny])
                    box[nx][ny] = box[x][y] + 1
                else:
                    continue


m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

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


day = 0
bfs(tomato)
for i in box:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    day = max(day, max(i))
print(day - 1)

이 풀이도 똑같이 bfs를 활용했다.

다른 점은 좌표를 차례대로 queue인 tomato에 저장해주고, bfs를 하는 도중 다음 좌표의 box 값이 0이라면 원좌표의 값에 +1을 해주는 방식을 사용했다. 

 

또한 이 방식도 처음 토마토의 위치가 1이어서 하루가 더 더해진 방식이므로 box에 0이 없음을 확인하면 1을 뺀 값을 출력해준다.