티스토리 뷰

반응형

 

 

 문제

 

www.acmicpc.net/problem/7576

 

7576번: 토마토

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

www.acmicpc.net

 

 

 

 

 

 

 문제 상황

 

- 토마토가 다 익는데 걸리는 최소 시간을 출력하고, 불가능하다면 -1을 출력한다.

 

 

 

 

 

 

 

 해결 전략

 

- 우선 0의 개수를 계산하여 전부 익었는지 확인하는데 사용한다. 그리고 같은 시간에 익는 토마토의 위치들을 새로운 큐에 넣어 작업을 반복한다.

 

 

 

 

 

 

 

 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from sys import stdin
from collections import deque
input = stdin.readline
M, N = map(int, input().split())
farm = [ list(map(int, input().split())) for _ in range(N) ]
visited = [[-1 for i in range(M)] for j in range(N)]
cnt = 0 # 0의 개수
sec = 0 # 익는데 걸리는 시간
riping = deque()
temp = [] # 같은 시간안에 처리되어야할 목록
for i in range(N): # 0의 개수 구하기
    for j in range(M):
        if farm[i][j] == 0 : 
            cnt += 1
            visited[i][j] = 0
        if farm[i][j] == 1 : temp.append((i,j))
riping.append(temp)
def bfs(x,y):
    global cnt
    dx, dy = [-1,1,0,0], [0,0,1,-1]
    temp = []
    for i in range(4):
        xx,yy = x+dx[i], y+dy[i]
        if 0<=xx<and 0<=yy<M:
            if visited[xx][yy] == 0 and farm[xx][yy] == 0:
                visited[xx][yy] = 1
                farm[xx][yy] = 1
                temp.append((xx,yy))
                cnt -= 1
    return temp    
while riping and cnt != 0:
    check = riping.popleft()
    sec += 1
    temp = []
    for i in range(len(check)):
        x, y = check[i]
        temp.extend(bfs(x,y))
    if len(temp) !=0 : riping.append(temp)
print(sec if cnt == 0 else -1)
cs

 

 

 

 

 

 

 

 

 해설

 

- 한번에 작동되는 부분이 여러개이므로 이를 동시에 처리하기 위해 temp 리스트를 만들어서 같은 시간에 동작하는 리스트를 선언하였다. 이후 cnt가 0이 아닌 조건, 즉 익어야할 토마토의 남은 개수가 존재할 때 사방을 탐색하며 작업을 반복한다.

 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 재귀가 직관적이지만 아직까지 논리를 생각하기는 반복문이 더 쉽다.

 

 

 

 

 

 

 

 

반응형
댓글