https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
풀이
- bfs를 실행하게 되면 배열을 해당 모습으로 값이 변한다.
- 1(익은 토마토)가 담겨있는 곳을 큐에 담는다.
- 주변에 0(익지 않은 토마토)이 존재할 때 하루 지났다는 의미로 해당 위치에 1을 증가시킨 값을 집어넣는다.
- 배열에 있는 최대값을 저장하여 1을 빼준 값이 토마토가 모두 익은 날이 된다.
코드
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1001
#define _X first
#define _Y second
int board[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int M, N; // 가로, 세로
int maxDay = 0;
int day = 0;
queue<pair<int, int>> q;
void Bfs()
{
while (!q.empty())
{
pair<int, int> cur = q.front();
int x = cur._X;
int y = cur._Y;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 범위를 벗어났다면
if (board[nx][ny] == -1) continue; // 토마토가 없다면
// 익지 않은 토마토가 있을 경우,
if (board[nx][ny] == 0)
{
board[nx][ny] = board[x][y] + 1;
q.push({ nx, ny });
}
}
}
}
// 익지 않은 토마토가 있는지 확인하고 모두 익었으면 일수 출력
void CheckBoard()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
// 익지 않은 토마토가 있을 때는 -1 출력 후 for문 탈출
if (board[i][j] == 0)
{
cout << -1;
return;
}
// 배열의 값을 저장하는 day 변수가 최대 일수보다 크다면 바꿔준다.
day = board[i][j];
if (maxDay < day)
maxDay = day;
}
}
// 익은 토마토가 1이기 때문에 일수를 구하기 위해서는 1을 빼줘야 한다.
cout << maxDay - 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 가로, 세로 입력
cin >> M >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
// 배열 입력
cin >> board[i][j];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (board[i][j] == 1)
{
// 익은 토마토가 있으면 큐에 넣음
q.push({ i, j });
}
}
}
Bfs();
CheckBoard();
return 0;
}'C++ > BFS, DFS' 카테고리의 다른 글
| [C++] 백준 2606 - 바이러스 (0) | 2022.12.25 |
|---|---|
| [C++] 백준 7569 - 토마토 (3차원) (0) | 2022.12.12 |
| [C++] 백준 5014 - 스타트 링크 (0) | 2022.12.06 |
| [c++] 백준 2468 - 안전 영역 (1) | 2022.12.06 |
| [C++] 백준 10026 - 적록색약 (0) | 2022.12.05 |