인프런 커뮤니티 질문&답변

선생님 풀이 보기 전에 두가지 방법으로 풀었는데 두 방법모두 4, 5번 input에 대해 시간초과가 나옵니다 대량 3~4초씩 걸립니다 ㅠㅠ

두가지 방법 하나는 선생님 풀이와 사소한 부분을 제외하면 같은 방식이고, 다른 하나는 pair를 사용해서 level을 올리는 방식으로 했습니다. 두번째 방식 코드 올려봅니다.

왜 시간초과가 생기는 것일까요..?ㅠㅠ

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

struct Pos
{
	bool operator==(const Pos& other)
	{
		return y == other.y && x == other.x;
	}

	bool operator!=(const Pos& other)
	{
		return !(*this == other);
	}

	Pos operator+(const Pos& other)
	{
		Pos tmp = *this;
		tmp.y = tmp.y + other.y;
		tmp.x = tmp.x + other.x;
		return tmp;
	}

	int y;
	int x;
};

Pos front[4] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
};

int main(void)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	freopen("in5.txt", "rt", stdin);  // 파일 입력받음

	int n, m;  // n은 상자 세로, m은 상자 가로
	cin >> m >> n;

	vector<vector<int>> box(n, vector<int>(m));
	queue<pair<Pos, int>> q;
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
		{
			cin >> box[y][x];
			if (box[y][x] == 1)
			{
				q.push(make_pair(Pos{ y, x }, 0));
			}
		}
	}

	int now_lv;
	while (q.empty() == false)
	{
		pair<Pos, int> tmp = q.front();
		q.pop();

		Pos now = tmp.first;
		now_lv = tmp.second;

		for (int dir = 0; dir < 4; dir++)
		{
			Pos next = now + front[dir];

			if (next.y<0 || next.y>n - 1 || next.x<0 || next.x>m - 1)
				continue;

			if (box[next.y][next.x] == -1 || box[next.y][next.x] == 1)
				continue;

			box[next.y][next.x] = 1;
			q.push(make_pair(next, now_lv + 1));
		}
	}

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
		{
			if (box[y][x] == 0)
			{
				cout << "-1";
				return 0;
			}
		}
	}

	cout << now_lv;
}