[백준] 7576번 토마토 (Python)

2021. 3. 11. 19:15·알고리즘/백준
728x90
반응형

문제

 

www.acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

코드

 

# 출력 : 토마토가 모두 익을 때까지의 최소날짜 출력
#        만약, 저장될 때 부터 모든 토마토가 익어있는 상태라면 0출력
#        토마토가 모두 익지는 못하는 상황이면 -1출력

from collections import deque
checker = True 
M, N   = list(map(int, input().split())) # M : 넓이 , N : 높이
tomato = [] 
for _ in range(N):
    tomato.append(list(map(int, input().split()))) # [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1]]


q = deque() # 익은 토마토를 담을 큐 생성

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1: # 익은 토마토 큐에 추가
            q.append([i,j]) # deque([[3,5]])


dx = [0,0,1,-1] 
dy = [1,-1,0,0]
# dx[0],dy[0] = (0,1) 오른쪽
# dx[1],dy[1] = (0,-1) 왼쪽
# dx[2],dy[2] = (1,0) 아래쪽
# dx[3],dy[3] = (-1,0) 위쪽

time = -1   # 출력값 : 걸린 날짜
            # -1로 시작하는 이유는 bfs로 검사 했을경우 이미 다 익은 토마토인 경우에는 걸린날짜 0을 리턴해주기 위함

# bfs   
def bfs(q, time):    
    while q: # 큐가 빌때 까지 계속 돌음
        time += 1 
        for _ in range(len(q)): # 큐에 길이만큼 반복 왜냐하면 익은 토마토가 여러개 있을 수 있기 때문에
            a, b = q.popleft()
            
            for i in range(4):  # 상하좌우 확인
                nx = a + dx[i]
                ny = b + dy[i]
                
                if (0 <= nx < N) and (0 <= ny < M) and tomato[nx][ny] == 0: # 범위가 안넘어가면서 안익은 토마토일 경우 큐에 추가하고 익혀줌
                    q.append([nx, ny])
                    tomato[nx][ny] = 1
    return time

time = bfs(q, time)
               

for i in tomato: # tomato = [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
    if 0 in i: # i안에 0이 있을경우는 토마토가 모두 익지 못한경우이다.
        checker = False
        print(-1) # -1 출력
        break

if checker:
    print(time)

 

코드설명

상자안에 토마토가 모두 익을 때 까지의 최소일수 출력

 

익은 토마토 주변으로 찾아나가야 하기 때문에 bfs로 풀 수 있다.

익은 토마토를 큐에 넣어주고 빼준 좌표를 기준으로 상하좌우를 모두 탐색해주고 범위안에 안익은 토마토가 있을시 큐에 넣어준뒤 tomato 리스트안에 값을 1로 변경해준다. 그리고 큐안에 값이 없을 때 까지 위 과정을 계속 반복한다.

 

tomato 리스트 안에 1개라도 0에 값이 있다면 모두 익지 못한 경우이기 때문에 -1을 출력한다.

 

그게 아니면 일수를 출력하면 된다.

 

다른풀이

import collections
m, n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
distance = [[0] * m for _ in range(n)]

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

def bfs():
    while queue:
        x,y = queue.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 and distance[nx][ny] == 0:
                    graph[nx][ny] = 1
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx,ny))

for x in range(n):
    for y in range(m):
        if graph[x][y] == 1:
            queue.append((x,y))

bfs()
checker = True
for i in graph:
    if 0 in i:
        print(-1)
        checker = False
        break

curMax = 0
for i in distance:
    curMax = max(curMax, max(i))

if checker:
    print(curMax)
반응형
저작자표시 (새창열림)

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 1011번 Fly me to the Alpha Centauri (Python)  (1) 2021.03.12
[백준] 2839번 설탕배달 (Python)  (0) 2021.03.12
[백준] 1316번 그룹단어체커 (Python)  (0) 2021.03.12
[백준] 1874번 스택 수열 (Python)  (0) 2021.03.10
[백준] 11651번 좌표정렬하기2 (Python)  (0) 2021.03.09
'알고리즘/백준' 카테고리의 다른 글
  • [백준] 2839번 설탕배달 (Python)
  • [백준] 1316번 그룹단어체커 (Python)
  • [백준] 1874번 스택 수열 (Python)
  • [백준] 11651번 좌표정렬하기2 (Python)
wookcode
wookcode
공부한 내용들을 정리하고 기록하는 블로그입니다.
    반응형
  • wookcode
    wookcode
    wookcode
  • 전체
    오늘
    어제
    • 카테고리 (196) N
      • study (1) N
        • 아파치 카프카 애플리케이션 프로그래밍 with 자.. (0)
        • 인프런 (1) N
      • Live Study (15)
      • Programming (14)
        • Java (8)
        • Python (1)
        • Springboot (5)
        • MSA (0)
      • 알고리즘 (117)
        • 백준 (58)
        • 프로그래머스 (59)
      • 에러로그 (5)
      • 항해99 (23)
      • 면접 (1)
      • 프로젝트 (1)
      • CS (19)
        • 네트워크 (2)
        • 운영체제 (2)
        • 데이터베이스 (2)
        • 컴퓨터구조 (1)
        • Java (8)
        • Spring (4)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    김영한
    회고
    항해99
    해결
    프로그래머스
    파이썬
    미니프로젝트
    그리디
    괄호
    조합
    정리
    브루트포스
    버그
    jpa
    orm
    에러
    SpringBoot
    카카오인턴
    카카오코딩테스트
    백준
    실전프로젝트
    spring
    인프런
    항해마켓
    알고리즘
    java
    SFlash
    스파르타코딩클럽
    코딩테스트
    후기
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
wookcode
[백준] 7576번 토마토 (Python)
상단으로

티스토리툴바