[알고리즘/BFS & DFS] 7576번 : 토마토 - python

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

7576번: 토마토

 

---

• 문제
• 소요시간: 35분 22초

---

• 설계하기(접근방법) 

1. 입력받기

토마토 행렬을 입력받는다

 

2. 구현하기

-1이 있는 구역은 ripe를 전달하지 못한다

1이 여러 군데 있는데, 이 부분은

bfs 시작시 q에 append를 여려 개 해주면 된다.

 

매 시도마다 토마토를 다 확인하는 것은 불가능하다

즉 토마토의 개수를 미리 세두면 된다

 

이미 익은것과

익지 못하는 구간을 빼면

전체 배열에서 앞의 둘을 빼면

앞으로 익을 토마토의 개수이다.

 

만약 실제로 bfs를 돌렸을 때 익을 토마토의 개수보다 모자라다면

익지 않은 토마토가 있는지 없는지 구할 수 있다

 

그 부분을 유의해서 bfs를 돌리고 

visited의 최대값을 구하면 된다

 

+++

bfs가 돌아가지 않는 경우 max값을 구하지 못하는 경우가 있었다.

checker를 둬서 체크해주었다

 

 

 

3. 출력하기

 

 

 

---

• 코드(출력)

from collections import deque

y, x = map(int,input().split())

graph = []
visited = [[0 for _ in range(y)] for _ in range(x)]
tmt_start = []
tmt_total = x * y
tmt_cnt = 0

for i in range(x):
    tmt_list = list(map(int, input().split()))
    for j in range(y):
        if tmt_list[j] == 1:
            tmt_start.append([i,j])
            visited[i][j] = 1
            tmt_cnt +=1
        if tmt_list[j] == -1:
            tmt_total -= 1
    graph.append(tmt_list)
    

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
while tmt_start:
    q.append(tmt_start.pop())

max_x = x
max_y = y
bfs_checker = 0
while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < max_x and 0<= ny < max_y and visited[nx][ny] == 0:
            if graph[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                bfs_checker = 1
                q.append([nx, ny])
                tmt_cnt += 1
                max = visited[nx][ny]

if tmt_total == tmt_cnt:
    if bfs_checker == 1:
        print(max - 1)
    else:
        print(0)
else:
    print(-1)

---

• 얻어갈 부분

1. 앞으로 행렬 길이를 받을 때 꼭  m,n으로 받자. 중간에 또 틀릴 뻔했다