[백준 7576번-토마토]-파이썬

solved.ac 난이도 : GOLD5

백준      7576번- 파이썬 풀이

 

<문제>

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

7576번: 토마토

<풀이>-BFS,그래프 이론,그래프 탐색

이 문제는 여러곳에서 시작하는 bfs 문제로 난이도는 GOLD5 지만 크게 어렵지는 않았던 거 같다. 

 

하루가 지날때마다 인접한 토마토가 익는다 했으므로 토마토가 안익은 지역을 bfs를 통해 방문할때마다 +1을 해주고 그래프에서 가장 큰값을 찾으면 되는 문제였다.

 

이때 이문제에서 가장 중요한것은 토마토가 있는 모든 지역에서 동시에 인접한 지역으로 영향을 미친다는 것이다.

 

따라서 처음에 반복문을 통해 익은  토마토가 있는 지역을 큐에 삽입하고 차례로 큐에서 꺼내 bfs를 수행해야 한다.

 

그리고 그래프에서 -1인 부분은 토마토가 없는 칸이라 했으므로 만약 이동한 칸이 -1이라면 그냥 무시해주면 된다.(너무 복잡하게 생각할 필요가 없는 부분이다.)

 

728x90

반응형

<코드>-파이썬

from collections import deque
m,n = map(int,input().split())
tomato = []
for _ in range(n):
    tomato.append(list(map(int,input().split())))
queue = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            queue.append((i,j))


dx = [-1,0,1,0]
dy = [0,-1,0,1]
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 tomato[nx][ny] == -1:
                continue
            if tomato[nx][ny] == 0:
                queue.append((nx,ny))
                tomato[nx][ny] = tomato[x][y]+1
                
flag = False
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            flag = True
            break
if flag:
    print(-1)
else:
    print(max(map(max,tomato))-1)

만약 토마토가 전부 익지 못하는 상황일 경우 필자는 flag = False로 초기화 해 안익은 토마토가 하나라도 있는 경우 flag를 True로 만들어줬다. 

 

그리고 코드에서처럼 만약 flag가 True 인 상태라면 문제의 조건대로 -1을 출력했다.

 

 

-마치며-

bfs/dfs문제는 사실 가장 익숙한 문제라 bfs부분을 짜는데는 그렇게 어렵지 않았다. 하지만 어이없게도 문제에서 n,m을 입력받는 부분을 행과 열을 반대로 입력받아 한참 해매는 실수를 저질러 버렸다.

다음부턴 이런 실수는 절대 하면 안되겠다.