https://www.acmicpc.net/problem/7576
문제
> 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다.
> 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
> 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.
> 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.
> 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.
> 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
> 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때,
며칠이 지나면 토마토들이 모두 익는지,
그 최소 일수를 구하는 프로그램을 작성하라.
> 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.접근
그래프 탐색, 사방탐색을 이용헌다.
토마토의 보관 상태를 입력받으면서 상태가 1인, 즉 토마토가 들어있는 좌표를 모두 저장한다.
그래프 탐색의 시작 큐에 해당 위치를 모두 넣고 시작한다.
그럼 각각의 토마토에 대해 시간이 지날 때마다 어떻게 상태가 변하는지 알 수 있다.
문제해결
> 입력으로 주어진 창고의 크기, 토마토 보관 상태를 입력받는데 입력이 -1로 토마토가 없는 곳이 주어지면 이 위치에선 주변 토마토로 영향을 줄 수 없기 때문에 방문처리 벡터 bool에 1을 미리 저장한다.
> 입력이 1인 좌표는 토마토가 있는 곳이므로 주변에 영향을 주는걸 따져야하므로 이 좌표들을 모두 벡터에 저장해 모아둔다.
> 토마토의 상태를 처리하는 메소드 Tomato에 토마토가 있는 좌표들의 모음 벡터와 아직 0일 째 이므로 0을 인자로 받아 함수를 호출한다.
> 함수 내에선 입력받은 위치들을 반복문으로 전부 큐에 넣는다. 그럼 큐에 넣은 이 좌표들을 통해 각각의 토마토에 대해 while문에서 다음 영향을 주는 좌표를 구한다.
> 구한 좌표들이 범위 밖이면 무시하고, 이미 영향을 준 좌표(추가로 -1이었던 좌표도 이미 영향을 받았다(true상태)로 처리했기 때문에서 여기서 걸리진다)도 무시한다.
> 영향을 받는 좌표들이 다음으로 큐에 들어가면서 day값에 1씩 더해져서 몇일 차 인지 기록된다.
> 이렇게 모두 탐색이 끝나면 영향을 못받는 위치에 있는 토마토가 있는지를 봐야한다. visited벡터를 돌며 false인 좌표가 하나라도 존재하면 영향을 못받은 토마토가 있다는 뜻이므로 -1을 출력한다.
> 없다면 모두 잘 익었다는 뜻이고 day를 계산해놓은 rst값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M;
vector<vector<int>> tomato;
vector<vector<bool>> visited;
vector<pair<int, int>> ripe;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
struct some
{
int row;
int col;
int cnt;
};
void Tomato(vector<pair<int, int>> v, int day)
{
queue<some> q;
for (auto a : v)
{
q.push({ a.first, a.second, day });
visited[a.first][a.second] = true;
}
int rst = 0;
while (!q.empty())
{
int fr = q.front().row;
int fc = q.front().col;
int fday = q.front().cnt;
q.pop();
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= N) continue;
if (nc < 0 || nc >= M) continue;
if (!visited[nr][nc])
{
rst = fday + 1;
q.push({ nr, nc, rst });
visited[nr][nc] = true;
}
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (!visited[i][j])
{
cout << -1 << '\n';
return;
}
}
}
cout << rst << '\n';
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> M >> N;
tomato.resize(N, vector<int>(M));
visited.assign(N, vector<bool>(M, false));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
int tmp;
cin >> tmp;
if (tmp == 1) ripe.push_back({ i, j });
else if (tmp == -1) visited[i][j] = true;
tomato[i][j] = tmp;
}
}
Tomato(ripe, 0);
}
후기
다 잘 됐는데 rst값이 +1 인 상태로 나왔다.
Tomato 메소드를 따라가보니 사방탐색을 하는 for문 안에서 nr과 nc를 계산하고 바로 rst를 fday+1로 계산해놨었다.
이렇게 되면 사방탐색의 결과로 다음 탐색대상이 있든 없든 무조건 rst엔 하루 더 추가돼서 이미 다익었는데도 하루 경과된 결과로 나온다.
그래서 이를 다음 탐색대상을 걸러내는 조건문들 마지막에부에 넣었다.
이렇게 하면 모든 조건을 만족하고 다음 탐색이 있다면 rst가 갱신된다는거고, 다음탐색 대상이 없다면, 즉 모든 토마토에 대해 처리가 끝났다면 하루 추가되지 않고 맞게 결과가 나온다.
