문제 해석
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
위와 같이 6*4 크기의 토마토 박스가 있다.
여기서 0은 익지 않은 토마토, 1은 익은 토마토일 때,
익은 토마토의 상, 하, 좌, 우에 있는 토마토는 모두 하루가 지나면 익는다.
여기서 모든 토마토가 익는 데 걸리는 날짜를 출력하는 문제이다.
토마토 박스의 숫자를 '해당 토마토가 익은 날짜' 로 채우면,
9 8 7 6 5 4
8 7 6 5 4 3
7 6 5 4 3 2
6 5 4 3 2 1
마지막 토마토가 익는 날짜는 9일 차이다.
따라서 1일차부터 시작하여, 모든 토마토가 익는 데에는 8일이 걸린다.
8
출력값에서 이를 확인할 수 있다.
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
또 다른 케이스로, 이번에는 익은 토마토가 두 개이다.
이 때 -1이 주어진 칸은 토마토가 없는 칸이다.
토마토가 없는 칸은 주변에서 토마토가 익든 썩든 다른 토마토에게 영향을 주지 못한다.
마찬가지로 익는 날짜를 채우면 다음과 같다.
1 -1 7 6 5 4
2 -1 6 5 4 3
3 4 5 6 -1 2
4 5 6 7 -1 1
마지막 토마토가 7일 차에 익게 되므로, 모든 토마토가 익는 데 6일이 소요된다.
6
또 다른 케이스로는,
사방이 토마토가 없는 칸에 가로막혀 구조적으로 익지 못하는 토마토가 있는 경우에는 -1을, 또는 주어진 1일차 토마토박스가 이미 모두 익은 경우라면 0을 출력하게 된다.
혼자 힘으로 풀어보려 했지만,, 한시간,,, 두시간,,,, 흘러갔다.
깨달음을 얻고 10분컷을 하게 해주신 티스토리와 벨로그 선생님들 그리고 GPT 교수님께 감사를 전하며..
뭐가 쓰일까요
이 문제에서 쓰이는 중요한 포인트를 다음과 같이 뽑을 수 있겠다!
- 최단거리 탐색과 같은 맥락? → BFS
- dx, dy를 이용한 이동 알고리즘
- 익은 날짜를 tomato 배열에 다시 저장
익은 토마토에서 다음 날 상하좌우에 있는 토마토가 익게 되는데,
이 때 dx, dy 배열을 이용한 이동 알고리즘이 쓰인다.
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 }; // 시계방향 이동
...
while(!q.empty())
{
...
for (int i = 0; i < 4; i++)
{
int nextX = currX + dx[i];
int nextY = currY + dy[i];
...
}
}
...오늘의 익은 토마토 좌표를 currX, currY라고 하자.
for 문을 4번 돌며, currX와 currY에 dx[i], dy[i] 를 더해 nextX, nextY 를 설정한다. 예를 들어, i=0인 루프에서는 (0, -1) 을 더해주므로, 현재 좌표에서 위로 한 칸 이동하는 것과 같다.
따라서 for 문을 돌 때마다 next 좌표는 curr 좌표에서 (0, -1), (1, 0), (0, 1), (-1, 0) 씩 이동한 값들로 설정되며, 이는 각각 위, 오른쪽, 아래, 왼쪽으로 한 칸씩 이동하는 것과 같다.
익은 날짜를 저장하는 부분은 위의 문제 해석에서 써놓은 것과 같다.
그래서 어떻게 했는데
#include <iostream>
#include <queue>
using namespace std;
int M, N;
int tomato[1000][1000];
queue<pair<int, int>> q;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 }; // 시계방향 이동
void BFS();
int main() {
cin >> M >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> tomato[i][j];
if (tomato[i][j] == 1) {
q.push(make_pair(i, j));
// 익은 토마토 좌표 저장
}
}
}
BFS();
// 현재 tomato 배열에는 -1인 곳 제외하고 익은 날짜가 저장
int day = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (tomato[i][j] == 0) {
// 구조적으로 안익는 위치의 토마토가 남아있음
cout << -1 << "\n";
return 0;
}
day = max(day, tomato[i][j]);
// 토마토 배열의 최대값 찾기
}
}
cout << day - 1 << "\n";
// 익은 날짜에서 1을 빼야 익는데 걸린 날짜
return 0;
}전역 변수로 토마토 박스의 사이즈인 M, N, 토마토를 담을 배열 tomato[][], BFS에서 사용할 익은 토마토를 담는 큐 q, 앞서 언급한 dx, dy 배열을 선언하였다.
main 함수에서는 M, N을 입력받고 그 사이즈만큼의 1일차 토마토 정보를 입력받는다. 이 때 익은 토마토, 즉 tomato[i][j]==1 인 좌표를 큐에 push한다.
이후 BFS 함수를 돌면 tomato 배열에는 앞서 말했듯 해당 칸의 토마토가 익은 날짜가 저장된다. 여기서 최대값을 찾고, 그 값에서 -1을 하면 모든 토마토가 익는 데 걸린 날짜를 얻을 수 있다.
그러나 사방이 빈 칸으로 막혀서 구조적으로 안 익는 토마토가 존재할 때, -1을 출력하기 위해 for 문을 돌며 tomato 배열을 모두 체크한다. tomato[i][j]==0 인 칸이 있다면 그 즉시 -1을 출력하도록 했다.
void BFS() {
while (!q.empty()) {
int currX = q.front().first;
int currY = q.front().second;
// 현재 좌표 : 익은 토마토
q.pop();
for (int i = 0; i < 4; i++)
{
int nextX = currX + dx[i];
int nextY = currY + dy[i];
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M)
continue;
// 박스를 벗어난 좌표 예외처리
if (tomato[nextX][nextY] == 0) {
// 안익은 토마토면 익어야지
tomato[nextX][nextY] = tomato[currX][currY] + 1;
// 익은 날짜를 배열에 저장
q.push(make_pair(nextX, nextY)); // 큐에 넣음
}
}
}
}BFS 함수이다. 이 함수를 다 돌면 tomato 배열에는 해당 토마토가 익은 날짜가 저장된다.
BFS는 큐를 사용하여 구현하게 되는데, 큐에 특정 값을 넣어 그 값들을 이용하여 탐색을 하다가, 큐가 비었을 경우 반복문을 중지하여 탐색을 끝마치는 알고리즘이며, 이 문제처럼 최단거리 류 문제에 적합한 알고리즘이다. BFS와 DFS의 기본 원리는 이를 익힐 수 있는 문제인 백준 1260번에 대한 글에 자세히 나와 있어용 😙
while(!q.empty()) 반복문으로, 큐가 빌 때 까지 아래의 동작을 반복한다.
우선 큐의 제일 앞의 값을 currX, currY에 저장하는데, 이건 지금 while 루프에서의 현재 좌표라고 볼 수 있겠다.
그러고선 큐에서 그 값을 pop!
이후 for 문에서는 현재 좌표인 currX, currY에서 상하좌우로 한 칸씩 이동한 nextX, nextY를 설정한다.
이 좌표가 M*N 크기의 tomato 배열을 벗어난다면 continue로 해당 좌표에 대해서는 반복문을 진행하지 않도록 예외처리를 해 준다.
이 좌표의 토마토가 안 익었다면, tomato[nextX][nextY]에 tomato[currX][currY]+1 을 저장하여 해당 좌표의 토마토가 익은 날짜를 저장해준다!
이후 요 좌표를 큐에 넣고 새로운 while 루프를 돌게 된다.
이제 3차원 토마토 풀러 가야지!
풀면서 참고한 링크) https://seminzzang.tistory.com/97
