[백준][C++] 1260 토마토

1260. 토마토
문제 풀이

1260번: DFS와 BFS

 

토마토 전염병이 모두 퍼지는 최소 일수를 구하는 문제.

자료구조 시간에 배웠던 BFS로 풀 수 있었다.

 

알고리즘 설계

1. 입력받을 때 이미 익은 토마토의 좌표(y, x)를 queue에 넣어준다.
2. 이 때 익지 않은 토마토의 전체 개수를 센다.
3. queue가 empty가 될 때까지 현재 queue의 top에 인접한 좌표(사방)에 토마토들을 모두 익은 상태로 만들어준다.그리고 익힌 토마토의 개수를 센다.
4. 이 때 토마토들을 방문할 때 가장 중앙 토마토의 값 + 1을 대입해주고 queue에 넣어준다.
5. queue가 empty라면, 처음에 구했던 익지 않은 토마토의 전체 개수와 익힌 토마토의 개수가 같은지 확인한다.같다면 토마토 배열에 있는 값의 최댓값 - 1을 출력한다! (최단거리)
6. 같지 않다면, 모든 토마토를 익히지 못한 것!

 

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

배열의 값을 중앙+1로 하는 아이디어는 미로 탐색 문제를 풀 때를 이용했다!

 

코드

#include<iostream>
#include<queue>
using namespace std;

int width, height;

// 토마토 
int field[1000][1000];
// 방문 체크 배 
bool visited[1000][1000];

int curTomato, tomatoSum = 0;

// 사방 
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };

queue<pair<int, int>> q;

void Tomato(int x, int y);


int main()
{
    int answer = 0;
    cin >> width >> height;

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            cin >> field[y][x];
            visited[y][x] =열 false;

            // 익혀야하는 토마토 저장 
            if (field[y][x] == 0) tomatoSum++;
            // 이미 익은 토마토는 queue에 넣어준다 
            else if (field[y][x] == 1) q.push({ x,y });
        }
    }

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 익은 토마토이고 방문하지 않았을 때 
        if (field[y][x] > 0 && !visited[y][x])
        {
            Tomato(x, y);
        }

        answer = field[y][x];
    }

    // 익혀야하는 토마토를 익히지 못했을 때 -1 
    if (tomatoSum == curTomato)
    {
        cout << answer - 1;
    }
    else
    {
        cout << -1;
    }
}

void Tomato(int x, int y)
{
    visited[y][x] = true;

    // 사방 검사 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;

        // 방문하지 않았고 익지 않았다면 
        if (!visited[ny][nx] && field[ny][nx] == 0)
        {
            curTomato++;
            field[ny][nx] = field[y][x] + 1;
            q.push({ nx, ny });
        }
    }
}

 

BFS에서 인접한 노드들에게 센터 + 1을 대입하는 아이디어는 항상 신기하고 활용하기 좋은 것 같다.