JArchive 프로그래밍 일기

문제

토마토 백준 7576

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int m, n, totalcnt, sweetcnt;
int day = 1e9;
int box[1002][1002];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
queue<pair<pair<int,int>, int>> qu; // {좌표, 일수}

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < m);
}

void bfs(){
  while(!qu.empty()){
    int cx = qu.front().X.X;
    int cy = qu.front().X.Y;
    int cday = qu.front().Y;
    qu.pop();
    sweetcnt++;

    day = cday;
    //cout << "sweetcnt:" << sweetcnt << '\n';

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

      if(!checkrange(nx, ny) || box[nx][ny] != 0) continue;
      box[nx][ny] = 1; // 익히기
      qu.push({{nx, ny}, cday+1});
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> m >> n; // 가로, 세로

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++) {
      cin >> box[i][j];
      if (box[i][j] != -1) totalcnt++; // 토마토 총 개수 세기
      if (box[i][j] == 1) {
        qu.push({{i, j}, 0}); // 익은 토마토는 시작점
      }
    }
  }

  if(totalcnt == sweetcnt) cout << 0;
  else bfs();

  if(totalcnt == sweetcnt) cout  << day;
  else cout << -1;

  return 0;
}

리뷰

입력 받을 때 총 토마토의 개수를 세 둔다.
토마토가 모두 익지 않았을 때 -1을 출력해야 하기 때문이다.
익은 토마토의 주변에 있는 토마토를 익힐 수 있으니까 처음에 입력받을 때 '익은 토마토의 좌표'를 모두 큐에 넣는다.

bfs를 수행할 때, 큐에는 좌표와 날짜를 함께 저장한다. 

좌표의 유효범위를 확인하고, 안익은 토마토가 있으면 익은 것으로 바꾼다. 

문제

토마토 백준 7576번

리뷰

토마토가 최소 몇 일이 지나야 다 익을 수 있는지 출력하는 문제다.

익은 토마토가 1개로 시작하는 줄 착각하고서 헤맸다. 진짜... 문제를 정독해야겠다.

시작점이 반드시 하나라고 생각해서 1시간 동안 붙잡고있었는데 계속 틀렸다.

시작점을 큐에 push 하고 시작하고나서야 맞출 수 있었다.

처음에 토마토 값들을 (0 , -1, 1 ) 입력받을 때, 1이면 이미 익은 것이니까 이 지점들을 시작으로 상하좌우가 익어간다.

그래서 큐에 BFS 시작점으로써 넣어준다.

boundary 함수는 M * N 상자 범위를 벗어나는지 여부를 1 / 0 으로 알려준다.

큐에서 하나씩 꺼내서 상하좌우를 살피는데, 범위 안에 있고 아직 안익었다면( 0이라면 ) ripe 익혔다고 세준다.

그리고 만약 day 가 증가됬다면 갱신해준다.

day를 그냥 출력하면 맞출 줄 알았는데, 처음에 시작점은 이미 값을 1로 갖고 있으니까, 하루가 지나도 2가 되버린다.

M * N 크기의 A 배열이 어떻게 변해가는지 출력해보면서 발견했다.

그래서 마지막에 day - 1 을 해준다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1000+1 

using namespace std;

int M, N; // 가로, 세로 
int A[MAX][MAX];
int zero_cnt, ripe, day;

queue<pair<int,int> > q;

// 상 하 좌 우
int diff_x[4] = {-1, 1, 0, 0};  // N  
int diff_y[4] = {0, 0, -1, 1};  // M


bool boundary(int x, int y){ // M * N 범위 초과 하는지 확인 
    bool res = (x < N && x >= 0 && y < M && y >= 0) ? 1 : 0;
    return res;
}

void BFS(){

    while(!q.empty()){

        pair<int,int> now = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){ // 상하좌우 확인 

            int x = now.first + diff_x[i];
            int y = now.second + diff_y[i];

            if(boundary(x, y) && A[x][y] == 0){ // 범위 안에 있고, 안 익었으면. 
                A[x][y] = A[now.first][now.second] + 1; 
                q.push(make_pair(x, y));
                ripe++; // 익은 개수 
                day = max(A[x][y], day); // day 증가됬다면 갱신 
            }
        }

    }

    if(zero_cnt > ripe) { // 모두 익지 못한다. 
        cout << -1; 
    }else{
        cout << day-1;
    }

}

int main(void){

    cin >> M >> N; // 가로, 세로  

    for(int i = 0; i < N; i++){ // 세로 N

        for(int j = 0; j < M; j++){ // 가로 M 

            scanf("%d", &A[i][j]);
            if(A[i][j] == 0) zero_cnt++; // 안익은 토마토 개수 센다  
            else if(A[i][j] == 1) {
                q.push(make_pair(i, j)); // 가능한 시작점 모두 넣는다  
            }
        } 
    } // 입력받기 끝

    if(zero_cnt == 0) cout << 0; // 저장될 때부터 모든 토마토가 익어있는 상태
    else{ // 탐색시작 
        BFS(); 
    }

    return 0;    
}