[백준] 7576번 : 토마토

문제

 

---

풀이

 

myunji.tistory.com/284

[백준] 2178번 : 미로 탐색

이 문제랑 풀이가 거의 똑같다.

 

다만 모든 토마토를 방문하지 못할 수도 있는 경우를 체크해줘야 한다는 것과

가장 마지막에 익을 토마토(도착점)이 무엇인지 모른다는 것만 다르다.

---

소스코드

 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

//범위 초과 때문에 상하좌우 한줄씩 추가
int matrix[1002][1002];
int N, M;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

int bfs(vector<pair<int, int>> starts) { //큐로 구현
    int day; //날짜 계산
    queue<pair<int, int>> q;

    for (int i = 0; i < starts.size(); i++) //1인 토마토 먼저 넣어줌
        q.push(make_pair(starts[i].first, starts[i].second));
    while (!q.empty()) { //큐에 들어있는 모든 원소에 대해 가능한 방향 체크
        int row = q.front().first;
        int col = q.front().second;
        day = matrix[row][col] - 1; //날짜 갱신
        q.pop();
        for (int i = 0; i < 4; i++) { //상하좌우 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if (matrix[next_row][next_col] == 0) {
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (matrix[i][j] == 0) //익지 않은 토마토가 있는지 확인
                return -1;
        }
    }
    return day; //모두 익었다면 최소 날짜 리턴
}

int main() {
    vector<pair<int, int>> starts;

    cin >> M >> N;
    for (int i = 0; i < N + 2; i++) //2차원 배열 초기화
        memset(matrix[i], -1, sizeof(int) * (M + 2));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 1) //1이라면 starts 벡터에 추가
                starts.push_back(make_pair(i, j));
        }
    }
    cout << bfs(starts);
}

전체 소스코드다. 2178번과 중복되는 부분은 설명하지 않겠다.

 

    for (int i = 0; i < N + 2; i++) //2차원 배열 초기화
        memset(matrix[i], -1, sizeof(int) * (M + 2));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 1) //1이라면 starts 벡터에 추가
                starts.push_back(make_pair(i, j));
        }
    }

먼저 2차원 배열을 -1로 초기화 해야 하기 떄문에 memset을 사용한다.

그리고 입력을 받으며 만약 입력값이 1일 경우 토마토 starts 벡터에 넣어준다.

2178번과 달리 시작점이 여러개일 수 있는 것이다.

 

int bfs(vector<pair<int, int>> starts) { //큐로 구현
    int day; //날짜 계산
    queue<pair<int, int>> q;

    for (int i = 0; i < starts.size(); i++) //1인 토마토 먼저 넣어줌
        q.push(make_pair(starts[i].first, starts[i].second));
    while (!q.empty()) { //큐에 들어있는 모든 원소에 대해 가능한 방향 체크
        int row = q.front().first;
        int col = q.front().second;
        day = matrix[row][col] - 1; //날짜 갱신
        q.pop();
        for (int i = 0; i < 4; i++) { //상하좌우 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if (matrix[next_row][next_col] == 0) {
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (matrix[i][j] == 0) //익지 않은 토마토가 있는지 확인
                return -1;
        }
    }
    return day; //모두 익었다면 최소 날짜 리턴
}

bfs 함수다.

앞서 말했듯이 시작점이 여럿일 수 있기 때문에 starts 벡터의 크기만큼의 반복문을 돌며 큐에 넣어준다.

 

        int row = q.front().first;
        int col = q.front().second;
        day = matrix[row][col] - 1; //날짜 갱신
        q.pop();

그리고 큐에서 값을 뺄 때 day도 갱신한다. 왜냐면 가장 마지막에 pop된 토마토가 익는데 가장 오래 걸린 토마토일 것이기 때문이다.

 

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (matrix[i][j] == 0) //익지 않은 토마토가 있는지 확인
                return -1;
        }
    }
    return day; //모두 익었다면 최소 날짜 리턴

while문을 빠져나온 뒤 혹시 익지 않은 토마토가 있는지 확인한다.

그렇다면 -1을 리턴하고, 아니라면 day를 리턴한다.