글 읽기 - pair가 느린편인가요??

rktkek456 6년 전 0

이 코드로 맞긴 했는데 200ms가 걸렸습니다.

반복문이 너무 많아서 그런가 싶어서 다른분들 코드 보니까 그런것 같지는 않더라구요

다른점은 pair 같은데

pair 보다는 크기가 2인 int형 배열 쓰는게 낫나요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;
queue<pair<int, int>> bin;
decltype(auto) setCase(int M, int N) {
	vector<vector<int>> tomatoCase = vector<vector<int>>(N, vector<int>(M, 0));
	int temp;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> temp;
			tomatoCase[i][j] = temp;
			if (temp == 1) {
				pair<int, int> temp = { i,j };
				bin.push(temp);
			}
		}
	}
	return tomatoCase;
}

decltype(auto) bfs(vector<vector<int>> tomatoCase) {
	int M = tomatoCase[0].size() - 1;
	int N = tomatoCase.size() - 1;
	int count = 0;
	pair<int, int> temp;
	while (bin.empty() != true) {
		int qSize = bin.size();
		bool checker = true;
		for (int k = 0; k < qSize; ++k) {
			int x = bin.front().first;
			int y = bin.front().second;
			bin.pop();
			if (x + 1 >= 0 && x + 1 <= N) {
				if (tomatoCase[x + 1][y] == 0) {
					tomatoCase[x + 1][y] = 1;
					temp = { x + 1, y };
					bin.push(temp);
					checker = false;
				}
			}

			if (x - 1 >= 0 && x - 1 <= N) {
				if (tomatoCase[x - 1][y] == 0) {
					tomatoCase[x - 1][y] = 1;
					temp = { x - 1, y };
					bin.push(temp);
					checker = false;
				}
			}

			if (y + 1 >= 0 && y + 1 <= M) {
				if (tomatoCase[x][y + 1] == 0) {
					tomatoCase[x][y + 1] = 1;
					temp = { x, y + 1 };
					bin.push(temp);
					checker = false;
				}
			}

			if (y - 1 >= 0 && y - 1 <= M) {
				if (tomatoCase[x][y - 1] == 0) {
					tomatoCase[x][y - 1] = 1;
					temp = { x, y - 1 };
					bin.push(temp);
					checker = false;
				}
			}
		}
		if (checker == true)
			break;
		count += 1;
	}

	for (auto i : tomatoCase) {
		for (auto j : i) {
			if (j == 0)
				return -1;
		}
	}
	return count;
}

int main() {
	int M, N;
	cin >> M >> N;
	auto tomatoCase = setCase(M, N);
	cout << bfs(tomatoCase);
}