BOJ-백준 7576번 토마토

BOJ-백준 7576번 토마토

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

7576번: 토마토

 

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

 

 

✅ Python 정답 코드 입니다. 더보기 클릭!

from collections import deque
def bfs(q):
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]  
      ny = y + dy[i]
      if nx<0 or ny<0 or nx>m-1 or ny>n-1:
        continue 
      if box[nx][ny] == -1:
        continue
      if box[nx][ny] == 0:
        box[nx][ny] =box[x][y]+1
        q.append((nx,ny))
  return x,y

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

queue = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(m):
  for j in range(n):
    if box[i][j] == 1:
      queue.append((i,j))
try:
  x,y = bfs(queue)
  day = box[x][y]-1
except:
  day=0
for i in range(m):
  if 0 in box[i]:
    print(-1)
    break
else:
  print(day)

📌해설

BFS를 수행해 graph(상자)를 탐색합니다. 인접한 익지 않은 토마토를 BFS로 탐색하여 토마토가 모두 익는 일 수를 증가시킵니다. 

🚩주의

상자에 들어있는 토마토가 하나도 없을때(-1), x,y가 존재하지 않기 때문에 try except로 처리합니다. 

bfs 실행 후 하나라도 익지 않은 토마토가 상자안에 존재한다면 -1을 출력합니다.

 

from collections import deque
def bfs(q):
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]  
      ny = y + dy[i]
      if nx<0 or ny<0 or nx>m-1 or ny>n-1:
        continue 
      if box[nx][ny] == -1:
        continue
      # 안 익은 토마토가 있으면 큐에 append
      if box[nx][ny] == 0:
        box[nx][ny] =box[x][y]+1
        q.append((nx,ny))
  return x,y

1. 상하좌우를 탐색하는 bfs 함수를 작성합니다. 

1-1. 큐를 사용하기 때문에 collections deque를 import해줍니다. 

1-2. q가 존재하지 않을때 까지 반복하는 while문을 작성합니다.

    1-3. q의 가장 왼쪽에 있는(가장 먼저 들어온) 원소를 popleft()해주고 x,y에 저장합니다.

    1-4. 상하좌우로 이동시켜주는 for 문을 작성합니다. 

        (1) 새로운 좌표(이동한 좌표) nx, ny를 생성합니다. 

        (2) nx, ny 가 box 내의 좌표가 아니라면 continue를 통해 다음 nx,ny를 생성합니다.

        (3) 토마토가 존재 하지 않는 좌표라면 continue를 통해 다음 nx,ny를 생성합니다. 

        (4) 안 익은 토마토가 존재하면 이전 좌표 box에서 하루를 증가시켜(+1) 새로운 좌표 box 값을 갱신합니다. 

        (5) 새로운 좌표를 큐에 append 시킵니다. 

1-5. 더이상 탐색할 좌표 큐가 존재하지 않으면 마지막 좌표 x,y를 반환합니다.

 

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

queue = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]

2. 탐색에 필요한 정보를 입력받고 필요한 변수를 선언 및 초기화 합니다.

2-1. n : box 가로, m: box 세로

2-2. dx, dy: 이동 offset

 

for i in range(m):
  for j in range(n):
    if box[i][j] == 1:
      queue.append((i,j))
try:
  x,y = bfs(queue)
  day = box[x][y]-1
except:
  day=0
for i in range(m):
  if 0 in box[i]:
    print(-1)
    break
else:
  print(day)

3. box를 모두 조회하는 for문을 작성합니다. 

3-1. 익은 토마토가 발견 되면 해당 좌표를 queue에 append시킵니다. 

3-2. try - except 문을 작성합니다.

    (1) bfs를 실행해서 x,y에 반환된 값을 저장합니다.

    (2) 마지막으로 익은 토마토에 누적된 일수를 day에 저장합니다(1부터 시작했기 때문에 -1해줍니다.)

    (3) 만약 box 안에 모든 토마토가 익지 않았거나 토마토가 하나도 들어있지 않으면 x,y에 저장되는 값이 없습니다. 따라서 except에서 day = 0으로 초기화 해줌으로써 Error 처리를 해줄 수 있습니다.

3-3. box를 순회해서 만약 0이라는 값이 하나라도 존재하면 익지 않은 토마토가 존재하는 것을 의미하므로 -1을 출력하고 for문을 종료 합니다.

3-4. for문에서 break가 실행되면 else문이 실행됩니다. day를 출력해줍니다.

 

::

 

DFS 에서 쉬운 문제들을 많이 풀어보고 난 뒤라서 그런지 BFS도 이해하기 쉬운 것 같아요!!