[백준/C++] 7576번 토마토 (BFS기초문제, 방문체크 순서, vector 사용하면 안되는 이유)

내가 정말 애정하는 문제 토마토이다. (링크)

 

BFS의 기초를 이해하기에 좋은 문제라고 생각한다. 

그리고 여러 코딩테스트(삼전,한화,CosPro 등)을 치루면서 토마토와 유사한 문제들을 자주 봐왔다.

 

코딩테스트 준비를 시작하는 사람들이라면 토마토 문제는 꼭 한 번 풀어보면 좋겠다. 

익은 토마토, 안익은 토마토 개수만 신경쓰면 되고 그 외에는 딱히 어려운 경우는 없다. 

 

bfs를 풀 때 가장 중요한 점이 있다. 바로 방문위치이다. 

queue에서 pop 할 때 방문체크를 하는 것과 queue에 넣어줄 때 방문체크를 하는 것에는 큰 차이가 있다. 

꼭 queue에 넣어줄 때 방문체크를 하자 

방문체크를 pop 할 때 하는 것은 중복된 값들을 처리하는 경우가 생겨 시간 초과와 같은 에러가 생길 수 있다. 

또는 루프에 갇힐 가능성도 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>

int map[1005][1005];
bool visit[1005][1005];
int Y, X;
struct info { int y, x, cnt; };
std::queue<info> tomato;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
int ripedTomato, notRipedTomato;


int main() {
	scanf("%d %d", &X, &Y);
	for (int y = 0; y < Y; y++) {
		for (int x = 0; x < X; x++) {
			scanf("%d", &map[y][x]);
			if (map[y][x] == 1) {
				ripedTomato++;
				tomato.push({ y,x,0 });
				visit[y][x] = true;
			}
			else if (map[y][x] == 0) notRipedTomato++;
		}
	}

	if (notRipedTomato == 0) { printf("0"); return 0; }
	int ans = 0;
	bool check = false;
	while (!tomato.empty()) {
		info cur = tomato.front();
		tomato.pop();
		if (cur.cnt == 0) cur.cnt = 1;
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i], nx = cur.x + dx[i];
			if (ny < 0 || nx < 0 || ny >= Y || nx >= X) continue;
			if (visit[ny][nx] || map[ny][nx] != 0) continue;
			map[ny][nx] = 1;
			visit[ny][nx] = true;
			tomato.push({ ny,nx,cur.cnt + 1 });
			notRipedTomato--;
		}
		if (notRipedTomato<=0) {
			ans = cur.cnt;
			check = true;
			break;
		}
	}
	if (!check) { printf("-1"); return 0; }
	printf("%d", ans);
	return 0;

}

 

그리고 vector를 사용하면 안되는 이유!!

 

사실 vector로도 동일한 함수를 구현할 수 있다. 

사실 오히려 vector가 더 유연한 함수이니까 더 좋은게 아닐까? 라고 생각할 수 있다. 

내가 그랬다. 

 

하지만 vector같은 경우에는 queue의 pop 대신에 erase(v.begin())을 사용해야 한다. 

이때 v.begin()때문에 vector의 길이만큼 n번 시간이 더 소요된다. 

그래서 코테를 준비하는 분들은 vector를 사용하고 싶은 욕심은 접어두길 바란다.