[백준] 7576번: 토마토

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

7576번: 토마토

 

BFS를 구현하는 건 어렵지 않은데, 출력이

 

저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고 (A),

토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 하고 (B),

둘 다 아니면 모든 토마토가 다 익을 때까지 걸린 시간을 출력한다. (C)

 

이 부분을 처리하는 게 좀 복잡했다.

 

A. 모든 토마토가 익어있는가?

아예 입력값을 받을 때, 0이 아닌 노드의 개수를 세서 저장해놓고 만약 이게 m*n (모든 노드의 개수)값과 동일하면 0을 출력하도록 했다.

 

B. 토마토가 모두 익지 못하는 경우

처음 check[][] 배열이 모두 0으로 초기화되어 있다.최종 check[][]값이 0인 경우는 

 a) 시작 노드거나 (처음부터 익은 토마토였거나)

 b) 토마토가 없는 상태(-1)이어서 아예 방문을 안했거나이다. 

 c) 토마토가 익지 못했다. 

여기서 c)인 경우가 있으면 토마토가 모두 익지 못한 상황이라 -1을 출력해야 하므로,

if(check[i][j] == 0 && graph[i][j] == 0)

로 처리해주었다. 

 

C. 토마토가 다 익을 때까지 걸린 시간

은 그냥 check[][]에 있는 최대값을 출력하면 된다. 

 

우선, 그래프 정보를 저장하는 graph가 있고, 

방문여부를 확인할 visited 이중 배열이 있고,

익은 토마토(1)로부터 가장 짧은 경로를 저장할 check 이중 배열이 있다.

 

주의할 점은, 익은 토마토가 여러 개인 경우, bfs 시작 시에 아예 큐에 한꺼번에 그 여러 개의 익은 토마토들을 넣어줘야 한다는 점이다. 

그래서 bfs를 호출할 때, 단순히 x, y좌표가 아닌 여러 개의 익은 토마토의 좌표를 (starts로) 한 번에 보내서, 한 번에 큐에 넣도록 했다. 

 

예를 들어 예시 3을 보면 

 

6 4

1 -1 0 0 0 0

0 -1 0 0 0 0

0 0 0 0 -1 0

0 0 0 0 -1 1

 

(0, 0)에 있는 익은 토마토에서 무작정 시작하면 (0,5)에 있는 토마토의 경로가 11인가로 찍힌다. ((3, 5)에서 시작해서 3이어야 하는데) 그래서 큐에

(0, 0) > (3, 5) > (0, 1) > (3, 5) ... 이렇게 저장될 수 있게 t=0에 익어있는 (0, 0)과 (3, 5)를 한꺼번에 먼저 넣어줘야 한다는 것. (다음 neighbor를 탐색하기 전에)

 

//7576

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

int m, n;
vector<int> graph[1000];
int visited[1000][1000] = { 0, };
int check[1000][1000] = {0, };

bool isInBound(int x, int y){
	
	if(x<n && y<m && x>=0 && y>=0){
		return true;
	}else{
		return false;
	}
}

void bfs(vector<pair<int, int> > starts){
	
	queue<pair<int, int> >q;
	// direction vector
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, 1, -1};
	
	for(int i = 0; i<starts.size(); i++){
		int x = starts[i].first;
		int y = starts[i].second;
		visited[x][y] = 1;
		check[x][y] = 0;
		q.push(make_pair(x,y));
	}
	
	while(!q.empty()){
		pair<int, int> node = q.front();
		q.pop();
		
		for(int i = 0; i<4; i++){
			int newx = dx[i] + node.first;
			int newy = dy[i] + node.second;
			if(isInBound(newx, newy)){	
				if(graph[newx][newy] == 0 && visited[newx][newy] == 0){
					visited[newx][newy] = 1;
					q.push(make_pair(newx, newy));
					check[newx][newy] = check[node.first][node.second] + 1;
				}
			}
		}
	}
}

int main(void){
	
	vector<pair<int, int> > starts;
	
	cin >> m >> n;
	cin.ignore();
	
	int count_one = 0;
	for(int i = 0; i<n; i++){
		string str;
		getline(cin, str);
		stringstream ss(str);
		
		int temp;
		while(ss>>temp){
			if(temp != 0){
				count_one++;
			}
			graph[i].push_back(temp);
		}
	}
	
	// 만약 모든 입력값이 1이면 0을 출력한다.  
	if(count_one == m*n){
		cout << 0 << endl;
		return 0;
	}
	
	for(int i = 0; i<n; i++){
		for(int j=0; j<m; j++){
			if(graph[i][j] == 1){
				starts.push_back(make_pair(i, j));
			}
		}
	}
	
	bfs(starts);
	
	// 최종 판단
	// 1. check[][] 에 0인데, 안익은 토마토(0)였다. -> 못익힌 것: -1 반환 
	// 2. check[][] 에 0이 없으면 가장 큰 숫자가 값이다.
	
	int largest = -1;
 	for(int i = 0; i<n; i++){
		for(int j =0; j<m; j++){
			if(check[i][j] == 0 && graph[i][j] == 0){
				cout << -1 << endl;
				return 0; 
			}
			if(largest<check[i][j]){
				largest = check[i][j];	
			}
		}
	}
	
	cout << largest << endl;
	return 0;

}

 

추가

다시 문제를 풀게 되어 새로운 코드와 해설을 추가한다. 

C언어를 사용하여 문제를 풀었기 때문에, q에 대한 구현이 되어 있다. 

#include <stdio.h>

int M, N;
int box[1000+10][1000+10];
//int visited[1000+10][1000+10];

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

typedef struct pos{
    int y;
    int x;
    int time;
}POS;

POS q[1000*1000+10];
int rp = 0, wp = 0;

void enq(int y, int x, int time){
    //printf("enq: (%d %d) %d\n", y, x, time);
    q[wp].y = y;
    q[wp].x = x;
    q[wp].time = time;
    wp++;
}

POS deq(){
    POS tmp = q[rp];
    //printf("deq: (%d %d) %d\n", tmp.y, tmp.x, tmp.time);
    rp++;
    return tmp;
}

int isEmpty(void)
{
    return wp == rp;
}

inv BFS(void){
    int max;
    while(!isEmpty()){
        POS cur = deq();
        max = cur.time;
        for(int i = 0; i<4; i++){
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];

            if(ny < 0 || ny >= N) continue;
            if(nx < 0 || nx >= M) continue;
            if(box[ny][nx] != 0) continue;
            //if(visited[ny][nx] != 0) continue;
            //printf("visit: (%d %d) = %d\n", ny, nx, box[ny][nx]);
            box[ny][nx] = cur.time+1;
            enq(ny, nx, cur.time+1);
        }
    }
    return max; // 이렇게 해주면 굳이 다시 for문 돌릴 필요 없음
}

int main(void){
    
    scanf("%d %d", &M, &N);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            scanf("%d", &box[i][j]);
            if(box[i][j] == 1){
                enq(i, j, 0);
                visited[i][j] = 1;
            }
        }
    }

    BFS();

    int max = 0; 
    for(int i =0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(box[i][j] == 0) {
                printf("-1"); return 0;
            }
            else{
                if(box[i][j] > max) max = box[i][j];
            }    
            //printf("%d", box[i][j]);
        }
        //printf("\n");
    }
    
    printf("%d", max);
    return 0;
}

bfs를 돌면서 토마토 박스를 채워준다.

일단 입력을 받을 때, 토마토가 있는 곳(1)의 좌표를 다 enqueue 해준 후에,

거기서부터 하나하나 bfs를 돌리며 토마토가 있는 곳(0)에 언제 익었는지 표시를 해준다.

 

이때, bfs를 돌릴 때 안익은 토마토가 있는 곳만 방문을 해줘야 한다는 점을 유의하자.

 

이렇게 bfs를 다 돌리고 나면

토마토가 원래 없던 곳은 그대로 -1

처음부터 있었던 곳은 1

나머지는 얼마 후에 토마토가 익었는지가 표시되어 있을텐데, 이 중 0이 있다는 것은 안익은 토마토가 존재한다는 소리이다.

 

만약 0이 없으면 가장 오래 걸린 토마토의 시간을 프린트하면 되고,

0이 있으면 -1을 프린트 하면 된다.