BOJ 7576 토마토 || 내 풀이와 거기에서 더 좋은 개선사항.

 

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

<처음 내 풀이>

//주의할점, 입력이 m 과 n이 반대로 주어진다
//다 돌리고 최대값이 1이면 출력 0을 한다
//다 돌리고도 0인 부분이 존재한다면 -1을 출력한다. 안익으니까
//board가 -1이 아닌데 0인 부분(거리가) 라고 해야겠지

#include <bits/stdc++.h>
using namespace std;

int board[1005][1005];
int dist[1005][1005];

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

int n, m;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int,int>> q;
    cin>>m>>n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            dist[i][j]=-1;
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>board[i][j];
            if(board[i][j]==1){
                q.push({i,j});
                dist[i][j]=0;
            }
        }
    }
    bool finish=true;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(board[i][j]==0){
                finish=false;
            }  
        }
    }
    if(finish==true){
        cout<<0;
        return 0;
    }
    
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(int dir=0; dir<4; dir++){
            int nx=cur.first+dx[dir];
            int ny=cur.second+dy[dir];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(dist[nx][ny]!=-1) continue;
            if(board[nx][ny]==-1) continue;
            dist[nx][ny]=dist[cur.first][cur.second]+1;
            q.push({nx,ny});
        }
    }
    int mx=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(board[i][j]!=-1 && dist[i][j]==-1){
                cout<<"-1";
                return 0;
            }
            mx=max(mx,dist[i][j]);
        }
    }
    cout<<mx;
}

처음에 이렇게 풀이하였는데, 

이 부분에서 dist 배열에 값을 설정하는 것과, 처음부터 모두 익어있을때 0을 출력하는 부분에 관련되어서 개선할 수 있는 부분이 있어서 그 부분에 대한 수정 코드를 첨부한다. 

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> m >> n;
  queue<pair<int,int> > Q;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j] == 1)
        Q.push({i,j});
      if(board[i][j] == 0)
        dist[i][j] = -1;
    }
  }
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist[nx][ny] >= 0) continue;
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(dist[i][j] == -1){
        cout << -1;
        return 0;
      }
      ans = max(ans, dist[i][j]);
    }
  }
  cout << ans;
}

이렇게 처음에 dist를 board의 값이 1이나 -1인 경우는 0으로 두고, board의 값이 0인 경우(즉 안 익은 토마토 일 경우) -1로 둔다면, 

만약 처음부터 다 익어있어서 0을 출력하는데도 문제가 없는 코드가 된다. 

이렇게 작성하면 코드가 훨씬 짧아진다. 

물론 내가 처음에 작성한데로 애초부터 모두 익어있는 경우를 판별해서 return을 하는것도 나쁘지는 않지만, 아래와 같은 방법이 있다는것도 이해하도록 하자.