https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 단순한 BFS에서 아주 조금 응용을 하면 쉽게 해결할 수 있는 문제였습니다. 그래프를 입력받을 때 토마토가 들어있는 좌표를 따로 tomato라는 deque를 만들어 저장한다면 쉽게 해결할 수 있었습니다. 그 후로는 일반적인 bfs문제를 풀 때처럼 bfs를 적용합니다. 다만 전체 상자 안에 토마토가 익으려면 며칠이 걸리는지를 물어보는 문제였기 때문에 while 문 안에 for _ in range(len(tomato))를 두어서 이 해당하는 for문을 벗어날 때만 하나씩 count를 증가시켜주면 됩니다. for문을 추가해주는 이유는 한 번에 즉 하루에 bfs로 탐색할 수 있는 양이 tomato라는 deque에 추가되기 때문에 이 deque의 전체가 비면 하루가 지난 것 이기 때문입니다. 추가적으로 bfs로 탐색 후 전체 그래프에서 0 즉 익지 않은 토마토가 하나라도 존재하면 -1을 출력해 줍니다. 소스코드는 다음과 같습니다.
소스코드
|
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
40
41
|
from collections import deque
def bfs(grpah, tomato):
count = 0
while tomato:
for _ in range(len(tomato)):
x, y = tomato.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if graph[nx][ny] == 0:
graph[nx][ny] = 1
tomato.append((nx, ny))
count += 1
return count
m, n = map(int, input().split())
graph = []
tomato = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
graph.append(list(map(int, input().split())))
for j in range(m):
if graph[i][j] == 1:
tomato.append((i, j))
day = bfs(graph, tomato)
numOfZero = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
numOfZero += 1
if numOfZero == 0:
print(day-1)
else:
print(-1)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 4963번: 섬의 개수(Python) (0) | 2022.01.15 |
|---|---|
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.14 |
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.12 |
| 백준 알고리즘 11723번: 집합(Python) (0) | 2022.01.10 |
| 백준 알고리즘 14499번: 주사위 굴리기(Python) (0) | 2022.01.10 |