작성
·
334
0
선생님 풀이 보기 전에 두가지 방법으로 풀었는데 두 방법모두 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;
}