[백준 7576] 토마토

아래처럼 queue<pair<int,int>> q 를 사용하고 while 문으로 감싸서 bfs를 돌린 이유는 

bfs 한번 돌릴때마다 day++를 해주기 위함이었다.

 

하지만 다시 생각해보니 day 자체를 queue의 pair<int,int> 와 같이 넣어주면 while 문으로 감쌀 필요도 없었다.

#include <iostream>
#include <queue>

#define SIZE 1001

using namespace std;

int map[SIZE][SIZE];

int M, N;

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

// ((y,x), day)
queue<pair<pair<int, int>, int>> q;

void solve()
{
    int ans = -1;

    int cury, curx, nexty, nextx;
    while (!q.empty())
    {
        cury = q.front().first.first;
        curx = q.front().first.second;
        int day = q.front().second;
        q.pop();

		// day 가 크면 ans 최신화
        if (day > ans)
        {
            ans = day;
        }

        for (int i = 0; i < 4; i++)
        {
            nexty = cury + dy[i];
            nextx = curx + dx[i];

            if (nexty < 0 || nexty >= N || nextx < 0 || nextx >= M)
                continue;

            if (map[nexty][nextx] == 0)
            {
                map[nexty][nextx] = 1;
                q.push(make_pair(make_pair(nexty, nextx), day + 1));
            }
        }
    }

	// 만약 남은 0 이 있으면 다 못 익은것
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            if (map[i][k] == 0)
            {
                cout << "-1";
                return;
            }
        }
    }

    cout << ans;
}

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

    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> map[i][k];
            if (map[i][k] == 1)
            {
                q.push(make_pair(make_pair(i, k), 0));
            }
        }
    }

    solve();

    return 0;
}

 

---

전형적인 완전탐색 BFS 문제

 

초반에는 시작점을 최신화 하지 않고 항상 1번째 날 시작점 그대로 사용해서 제출했는데 시간초과남

그래서 매번 BFS돌때마다 최신화된 시작점 즉, 새로운 최전방의 시작점들을 저장해

다음 BFS때 해당 시작점들에서만 4방향으로 확인하게 함

 

---

#include <iostream>
#include <queue>
#include <algorithm>
#define SIZE 1000

using namespace std;

int arr[SIZE][SIZE];
int N, M;
queue<pair<int,int>> start;

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

bool check() {
	for (int i = 0; i < M; i++) {
		for (int k = 0; k < N; k++) {
			if (arr[i][k] == 0) {
				return false;
			}
		}
	}
	return true;
}

void bfs() {
	queue<pair<int, int>> newstart;

	while(!start.empty()) {
		int starty = start.front().first;
		int startx = start.front().second;
		start.pop();

		// 4방향에 대해 조사
		for (int i = 0; i < 4; i++) {
			int newy = starty + dy[i];
			int newx = startx + dx[i];

			if (newx < 0 || newx >= N || newy < 0 || newy >= M) continue;
			else {
				if (arr[newy][newx] == 0) {
					arr[newy][newx] = 1;
					// 다음 턴 시작점들
					newstart.push(make_pair(newy, newx));
				}
			}
		}
	}
    
	start = newstart;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
			if (arr[i][k]==1) start.push(make_pair(i, k));
		}
	}

	int day = 0;
	while (!check()) {
		bfs();
		if (start.empty()) {
			cout << -1;
			return 0;
		}
		day++;
	}
	cout << day;
	return 0;
}