[백준/c++] 7576번: 토마토

문제 링크 - https://www.acmicpc.net/problem/7576

🌱 문제

🌱 풀이

• BFS함수 처음에 토마토값이 1인 좌표들 부터 queue 넣고, 그 queue를 기준으로 BFS를 돌도록 하였다.
• dist배열은 0부터 시작하고 BFS를 통해 다음 좌표의 dist=현재좌표의 dist+1를 함으로써 dist값이 날짜를 나타낸다.
• 처음에 dist를 전부 -1로 초기화함으로써 dist가 방문체크의 역할도 하게 된다. (-1이면 방문 안한것, 그 외의 값이면 방문했으니 패스하는식으로)
• BFS가 끝나고 dist배열의 최댓값이 모든 토마토가 익은 날짜가 된다(영원히 익지 못하는 토마토는 제외하고)
• BFS후에 dist배열을 돌면서 최댓값을 찾으면서 익지 않은 토마토를 발견하면 -1를 출력하고 main함수를 종료한다. (발견 못하면 마지막에 최댓값 출력!)

🥲 헷갈렸던점

• 예제 입력3번처럼 익은토마토가 각각 다른지점에서 여러개로 시작하는 경우에 BFS와 dist배열을 통해 날짜가 제대로 카운트 될 수 있는건지 헷갈렸다. BFS함수 처음에 tomato값이 1인 좌표들을 queue에 먼저 넣었고, queue에서 그 뒤에 인접 좌표들을 넣기 때문에 정상적으로 날짜를 기록 할 수 있었다. 여러지점에서 bfs가 시작되면 겹치지 않을까 걱정했지마느 더이상 dist값이 -1인인 지점을 못찾으면 bfs도 끝나기 때문에 원하는 결과를 얻을 수 있었다.
• 코드에서 cx,nx,cy,ny처럼 x,y의미를 가진 좌표들을 사용했는데 내 코드에서보면 cx,nx가 행의 인덱스 의미하고 cy,ny가 열의 인덱스를 의미한다. 그런데 문제를 풀다가 갑자기 실제 수학에서의 x,y좌표랑 헷갈려서 if(nx >= 0 && ny >= 0 && nx < n && ny < m) 이부분에서 n,m의 위치를 바꿔서 써서 헤맸다.
  기억하자!! 코드상에서의 좌표는 실제 좌표와 반대이다!!
  x가 행, y가 열!!!!

🌱 코드

//7576번: 토마토

/*
상자크기 가로 M, 세로 N
2<=M,N<=1,000
1 익은토마토
0 익지않은 토마토
-1 안들어있음
*/

#include <iostream>
#include <queue>
using namespace std;
int m,n;
int tomato[1000][1000];
int dist[1000][1000]; //방문체크이자 시작지점으로부터의 거리를 나타낸다
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

queue<pair<int,int>> q;
int answer;

void bfs(){
    for(int i=0; i<n; i++){ //j가 열 인덱스, i가 행 인덱스
        for(int j=0; j<m; j++){
            if(tomato[i][j]==1){
                q.push(make_pair(i,j));//(열인덱스,행인덱스) 순서로 푸쉬
                dist[i][j]=0;
            }
        }
    }

    while(!q.empty()){
        int cx=q.front().first;
        int cy=q.front().second;

        q.pop();

        for(int i=0; i<4; i++){
            int nx=cx+dx[i];
            int ny=cy+dy[i];

 
            if(nx >= 0 && ny >= 0 && nx < n && ny < m){

                if(tomato[nx][ny]==0 && dist[nx][ny]==-1){
                    dist[nx][ny]=dist[cx][cy]+1;
                    tomato[nx][ny]=1;
                    q.push(make_pair(nx,ny));

                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>m>>n; //m이 가로, n이 세로
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>tomato[i][j];
            dist[i][j]=-1; // 방문안한 좌표 -1로 초기화
        }
    }
    bfs();

    answer=-1;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){

            if(tomato[i][j]==0){ //bfs끝났는데 안익은 토마토 있으면 -1출력하고 종료
                cout<<-1<<"\n";
                return 0;
            }

            if(answer<dist[i][j])
                answer=dist[i][j]; //  최댓값 찾기
        }
    }
    
    cout<<answer<<"\n";
}