[BOJ] 7576. 토마토

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

7576번: 토마토

 

 

1. 해결방법

"""
1. 아이디어
- 입력받은 그래프에서 토마토가 있는 지점부터 for문을 돌려 BFS 처리는 할 것이다.
- 방문기록 체크하면서 돔.
- 방문기록이 False 경우와 방문하고자 하는 인덱스 값이 0인 경우에만 방문해서 인덱스 값을 +1로 하고 방문기록을 True로 한다.
- bfs를 완료하고 열 인덱스에 값이 0이 존재하는 경우, -1을 print

2. 시간복잡도
- O(N^2)

3. 자료구조
- 2차원 배열 : int[][], bool[][]
"""

 

 

2. 정답코드

입력 예제(1)

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력 예제(1)

8

 

입력 예제(2)

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력 예제(2)

-1

 

입력 예제(3)

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

출력 예제(3)

14

 

입력 예제(4)

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

출력 예제(4)

14

 

입력 예제(5)

2 2
1 -1
-1 1

출력 예제(5)

0

 

 

코드

import sys
from collections import deque
input = sys.stdin.readline


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

chk = [[False] * m for _ in range(n)]
answer = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


# bfs
def bfs():
    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny = ey + dy[i]
            nx = ex + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if chk[ny][nx] == False and graph[ny][nx] == 0:
                    chk[ny][nx] = True
                    graph[ny][nx] = graph[ey][ex] + 1
                    q.append((ny, nx))




# main
q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i, j))

bfs()

for v in graph:
    for vertex in v:
        if vertex == 0:
            print(-1)
            exit(0)
    answer = max(answer, max(v))

print(answer - 1)