[백준 7576] 토마토 cpp-py

문제
NxM의 격자에 토마토가 보관되어 있다. 토마토 중에는 잘 익은 토마토도 있고 아직 익지않은 토마토도 있다. 잘 익은 토마토는 익지않은 토마토에 영향을 주어 하루가 지나면 잘 익은 토마토 주위의 익지않은 토마토도 익게된다. 토마토의 주위는 상하좌우를 의미하며 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
이때 잘 익은 토마토에 의해 상자 안의 모든 토마토가 다 익으려면 며칠이 걸리는지 출력하라.

입력
첫째 줄에 상자의 크기 M, N이 주어진다. (2이상 1000이하)
둘째 줄부터 상자 안의 토마토에 대한 정보가 들어있으며 1은 잘 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어있지 않다.

출력
모든 토마토가 익을 때까지의 최소 날짜를 출력하고 처음부터 모든 토마토가 익어있다면 0을 출력한다. 또한 토마토가 모두 익지 못한다면 -1을 출력한다.

---

접근

잘 익은 토마토에서 인접한 안 익은 토마토를 찾기위해 BFS를 활용한다.

그리고 1을 시작으로 안 익은 토마토를 익힐 때 익힌 날짜를 적어준다. 이는 인접한 토마토 중 익은 토마토에 들어있는 수에 +1을 해주면된다.

 

구현

토마토의 정보를 입력받고 잘 익은 토마토가 있을 때 큐에 넣어준다.

queue<pair<int, int>> q;
cin >> M >> N;
for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
    	cin >> map[i][j];
        if(map[i][j]==1)
        q.push({ i,j });
	}
}

 

BFS를 실행한다.

익은 토마토를 기준(cy, cx)으로 상하좌우에 안 익은 토마토(0)이 있으면 (cy, cx)에 있는 값 +1을 해준고 큐에 넣어준다.

최종적으로 맵 내에서 최댓값이 토마토가 모두 익은 날이 된다.

	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (RangeCheck(ny, nx) && map[ny][nx] == 0) {
				map[ny][nx] = map[cy][cx] + 1;
				q.push({ ny,nx });
			}
		}
	}

 

맵을 탐색하여 안 익은 토마토가 여전히 남아있으면 -1을 출력하고 바로 메인 함수를 종료시키다.

그렇지 않다면 계속해서 최댓값을 찾고

최댓값-1을 출력한다. 왜냐하면 처음에 잘 익은 토마토가 1이었고 1부터 날짜를 카운트했기 때문이다.

	int answer = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			else if (map[i][j] > answer){
				answer = map[i][j];
				}
		}
	}

	cout << answer-1 << endl;

---

전체 코드

 

c++

#include <iostream>
#include<algorithm>
#include <vector>
#include<cstring>
#include<queue>
// 2/5
using namespace std;

const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

int N, M;
int map[1000][1000];

bool RangeCheck(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}
int main()
{
	queue<pair<int, int>> q;
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if(map[i][j]==1)
				q.push({ i,j });
		}
	}

	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (RangeCheck(ny, nx) && map[ny][nx] == 0) {
				map[ny][nx] = map[cy][cx] + 1;
				q.push({ ny,nx });
			}
		}
	}


	int answer = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			else if (map[i][j] > answer){
				answer = map[i][j];
				}
		}
	}

	cout << answer-1 << endl;
	return 0;
}

/*

*/

 

python

'''

'''
import sys
from _collections import deque
input = sys.stdin.readline

def range_check(y, x):
    return (y>=0 and y<N) and (x>=0 and x<M)

def BFS():
    q = deque()
    for y in range(N):
        for x in range(M):
            if tomato_map[y][x] == 1:
                q.append((y, x))

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]

    while q:
        cy, cx = q.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if range_check(ny, nx) and tomato_map[ny][nx] == 0:
                tomato_map[ny][nx] = tomato_map[cy][cx] + 1
                q.append((ny, nx))

    result = 1
    for y in range(N):
        for x in range(M):
            if tomato_map[y][x] == 0:
                return -1
            if tomato_map[y][x] > result:
                result = tomato_map[y][x]
    return result-1

M, N = map(int, input().split())
tomato_map = [list(map(int, input().split())) for _ in range(N)]

answer = BFS()
print(answer)