[BOJ/백준] 7576 토마토

● [문제번호 7576] 토마토

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

7576번: 토마토

 

● 알아야 할 것

: BFS

: pair 자료구조와 메소드

: queue 자료구조와 메소드

 

● 풀이 과정

: BFS를 이용하여 구현했다.

토마토가 들어 있는 상자(이하 토마토 지도)에서

다음 토마토 위치로 이동 불가능한 경우는 다음과 같다.

1. 토마토 지도의 X축을 벗어나는 경우

2. 토마토 지도의 Y축을 벗어나는 경우

3. 방문한 적이 있지만 기존보다 익는데 걸리는 시간이 더 긴 경우

4. 토마토가 들어있지 않은 경우

 

: DFS도 구현했지만 '시간 초과'를 벗어나기 어려운 것 같다.

왜냐하면 한 위치에서 DFS로 끝까지 갔다가 다음 위치로 들어가서 끝까지 갔다가하면

불필요한 실행과 실행시간이 많이 걸리는 것 같다.

 

구글링 해도 적절한 DFS 해법도 없는 것 같고,

해당 문제의 '알고리즘 분류'에서도 '깊이 우선 탐색'이 없는 것을 보니

주어진 제약조건에서 BFS로 풀어야 적절한 것 같다.

 

● 주의 할 것

: 초기 익은 토마토의 위치를 따로 저장해서

각 위치마다 BFS를 실행하면

불필요한 실행까지 하게 되어 '메모리 초과'를 받았다.

 

그래서 BFS 함수에서 Queue를 빼내어

BFS를 실행할 때 모든 시작점이 동시 실행하게 만들었다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 상자 칸에서 이동하기 위한 상, 하, 좌, 우
// controlY : 상자 칸에서 이동하기 위한 상, 하, 좌, 우
// tomato : 토마토를 저장할 격자 모양 상자
// q : DFS에서 사용할 Queue
// day : 토마토가 모두 익을 때까지의 최소 날짜
int controlX[4] = {-1, 1, 0, 0};
int controlY[4] = {0, 0, -1, 1};
int tomato[1001][1001];
queue<pair<int, int>> q;
int M, N, day;

// 넓이 우선 탐색
// 기본적인 작성 형태 + Queue 선언 및 출발점 저장위치 수정
void bfs()
{
    while(!q.empty())
    {
        int fromRow = q.front().first;
        int fromCol = q.front().second;
        
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int row = fromRow + controlX[i];
            int col = fromCol + controlY[i];
            
            // 진입하면 안되는 4가지
            // 1. X축을 벗어나는 경우
            if(row < 0 || N <= row)
                continue;
            // 2. Y축을 벗어나는 경우
            else if(col < 0 || M <= col)
                continue;
            // 3. 방문한 적이 있지만 익는데 걸리는 시간이 더 긴 경우
            else if(tomato[row][col] != 0 && tomato[row][col] <= tomato[fromRow][fromCol] + 1)
                continue;
            // 4. 토마토가 들어있지 않은 경우
            else if(tomato[row][col] == -1)
                continue;
            // {방문한 적 없거나} + {방문했어도 토마토가 익는데 걸리는 시간이 더 짧은 경우}만 진입
            else
            {
                tomato[row][col] = tomato[fromRow][fromCol] + 1;
                q.push(pair<int, int>(row, col));
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> M >> N;
    
    // 토마토 저장
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < M; c++)
        {
            cin >> tomato[r][c];
            
            // 출발점 미리 저장하여 모든 시작점 동시 실행
            // (왜냐하면 출발점이 1개 이상이니까)
            // (안그럼 '실행 초과'를 받았음)
            if(tomato[r][c] == 1)
                q.push(pair<int, int>(r, c));
        }
    }
    
    bfs();
    
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < M; c++)
        {
            // 안 익은 토마토가 있는 경우
            if(tomato[r][c] == 0)
            {
                cout << -1;
                return 0;
            }
            // 모든 토마토가 익는데 걸리는 시간 저장
            else
                day = max(day, tomato[r][c]);
        }
    }
    
    // 이미 익은 토마토를 1일 걸린거로 시작했기 때문에
    // 1일을 뺀다
    cout << day - 1;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277