#7576 토마토

문제는 위와같다(골드 5). 배운게 많았던 문제이다. dfs,bfs에대한 내 고정관념, 편협한 시각, 선입견, 아둔한 생각, 우둔한 사고, 굳어있는 코드 등을 깰 수 있었다. (ㅋㅋ)

 

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

int m,n,big;
int map[1001][1001];  //토마토 정보 입력 배열
int visited[1001][1001]; //방문기록
int date[1001][1001];  //최단 날짜
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<pair<int,int>> q;

void bfs(){
  //q.push(make_pair(y,x));
  //visited[x][y]=1;
  while(!q.empty()){
    int y=q.front().first; int x=q.front().second;
    q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k];
      int ny=y+dy[k];
      if(0<=nx&&nx<n && 0<=ny&&ny<m){  //범위 확인
        if(map[nx][ny]==0&&visited[nx][ny]==0){
          q.push(make_pair(ny,nx));
          visited[nx][ny]=1;
          date[nx][ny]=date[x][y]+1;
        }
      }
    }
  }
}

int main()
{
  freopen("input.txt", "r", stdin);
  int flag=-1; 
  cin>>m>>n;

  for(int i=0;i<n;i++){ //토마토 정보 입력
    for(int j=0;j<m;j++){
      cin>>map[i][j];
      if(map[i][j]==1){
        q.push(make_pair(j,i));
        visited[i][j]=1;
      }
    }
  }
  
  bfs();
  
  for(int i=0;i<n;i++){  //안익은거 있으면 -1 출력
    for(int j=0;j<m;j++){
      if(visited[i][j]==0&&map[i][j]==0){
        cout<<"-1"<<'\n';
        return 0;
      }
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(big<date[i][j]){
        big=date[i][j];
      }
    }
  }
  cout<<big<<'\n';
}

 코드는 위와같다. 문제는 어렵지 않았다. 토마토가 익는 최소 날짜를 찾는다는것은 그래프 상에서 최단거리를 찾는다는것과 비슷한 맥락으로 이해할 수 있었기 때문에 코드 구성은 쭉쭉 했는데 한 예제 에서 막혔다. 익은 토마토가 2개인 3번째 예제에서 bfs함수를 어떻게 동시에 돌리지? 라는 생각에 사로잡혀 한참을 헤맸다. 결론은 동시에 돌리는 방법은 없다! 였다. 

 

★ 배운 것

1. bfs는 동시에 돌리지 않아요.

3번째 예제 때문에 bfs를 동시에 호출하는것을 고민 했었다. 아무리 생각해도 모르겠었다. bfs는 큐를 이용한다. 그리고 한단계를 진행 할 때마다 q.front()를 이용하여 큐의 맨앞 원소를 뽑아 bfs를 이용하는 식이다. 이를 응용하면, 익은 토마토가 2개 이상이고, 이를 입력할때 익은 토마토인걸 알았다면 바로 q.push()를 해주어 bfs를 시작하기 전부터 큐에 넣어두는 것이다. 이러면 bfs를 시작할때 이미 큐에 익은토마토들의 정보가 저장되어있어 동시에 시작하는 효과를 얻을 수 있는것이다. 

 

2. bfs,dfs 는 꼭 인자를 필요로 하지 않아요.

여태껏 나는 dfs와 bfs를 코드로 구현할 때, 시작 점이나 시작 정점을 dfs,bfs함수의 인자로 넘기는 방식으로 구현했다. 그리고 함수 내에서 큐에 push하거나 하는 방식으로 했었다. 근데 이렇게 할 필요가 없다. 물론 시작점을 명확히 알고있고, 그 시작점이 하나라면 이 방식이 틀린것도 아니고 나쁜것도 아니다. 하지만 위의 문제와 같이 시작점이 두개 이상일때는, 함수를 동시에 돌릴수 없으므로, 아예 인자를 넘기지 않는다. 대신 함수 호출 전에 이미 조치를 취해 놓는 것이다.

 

3. 출력 초과!

백준 풀면서 처음 받아본 출력 초과. 알고보니 내가 행과 열때매 헷갈려서 map,visited,date 의 배열을 확인차 출력하는 코드를 넣었었는데 이걸 답으로 제출하니까 출력초과가 뜬거였다. 뭐 좋은 습관이니까 긍정적으로 생각해야징