3197 백조의 호수
문제 링크
- 내 풀이
백조 영역을 색칠하다가 빙산과 맞닿는 부분을 빙산 벡터에 넣는다.
물 벡터를 순환하며 빙산에 맞닿는 부분을 빙산 벡터에 넣는다.
문제점 : 이미 순환한 물 벡터를 또 방문하여 시간을 많이 잡아 먹어 시간이 오래 걸렸다. 그리고 빙산 벡터를 순환하는 시간도 잡아 먹혔다. 물의 방문 정보를 저장하면 시간을 절약할 수 있다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <ctime>
#define pii pair<int, int>
using namespace std;
constexpr int dr[4] = { 1, -1, 0, 0 };
constexpr int dc[4] = { 0, 0, 1, -1 };
int R, C;
int m[1500][1500], tm[1500][1500];
queue<pii> swan;
vector<pii> ibg, wtr;
int marking()
{
queue<pii> tmp;
int adjoin;
// marking swan area
while (!swan.empty())
{
adjoin = 0;
pii f = swan.front();
swan.pop();
int swan_num = m[f.first][f.second];
for (int d = 0; d < 4; d++)
{
int nr = f.first + dr[d];
int nc = f.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || m[nr][nc] == swan_num)
continue;
if (m[nr][nc] < 0)
{
adjoin = 1;
if (m[nr][nc] == -1)
{
ibg.push_back({ nr, nc });
m[nr][nc] = -2;
}
continue;
}
if (m[nr][nc] && m[nr][nc] != swan_num)
return 1;
m[nr][nc] = swan_num;
swan.push({ nr, nc });
}
if (adjoin)
tmp.push(f);
}
swan = tmp;
//cout << swan.size() << "\n";
//cout << wtr.size() << "\n";
//add water & iceberg boundary
for(pii f : wtr)
{
if (m[f.first][f.second] != 0)
continue;
for (int d = 0; d < 4; d++)
{
int nr = f.first + dr[d];
int nc = f.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || m[nr][nc] == 0)
continue;
if (m[nr][nc] < 0)
{
if (m[nr][nc] == -1)
{
ibg.push_back({ nr, nc });
m[nr][nc] = -2;
}
continue;
}
}
}
return 0;
}
void meltIceberg()
{
for (pii ice : ibg)
{
m[ice.first][ice.second] = 0;
wtr.push_back(ice);
}
ibg.clear();
}
void printm()
{
cout << "\n";
for (int r = 0; r < R; r++)
{
for (int c = 0; c < C; c++)
{
if (m[r][c] == -1)
cout << "X";
else
cout << m[r][c];
}
cout << "\n";
}
}
int solve()
{
int epoch = 0;
marking();
while (true)
{
if (marking())
break;
meltIceberg();
epoch += 1;
}
return epoch;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("in", "r", stdin);
cin >> R >> C;
string tmp;
int cnt = -1;
for (int r = 0; r < R; r++)
{
cin >> tmp;
for (int c = 0; c < C; c++)
{
if (tmp[c] == 'X')
{
m[r][c] = 1;
}
else
{
m[r][c] = 0;
if (tmp[c] == 'L')
{
m[r][c] = cnt;
cnt += -1;
swan.push({ r, c });
}
else
{
wtr.push_back({ r, c });
}
}
}
}
clock_t st, ed;
st = clock();
cout << solve() << "\n";
ed = clock();
cout << "time : " << ed - st << "\n";
return 0;
}
- 이분 탐색을 이용한 풀이(백준 질문/답변의 아이디어 활용)
빙산의 녹는 시간에 대한 정보를 미리 BFS 탐색을 하여 저장한다.
날짜에 따른 만남 여부를 판단하는 함수를 작성하고 이분탐색을 시행한다.
문제점 : 이분탐색을 시행할 때 마다 맵 정보를 다시 불러오는 탐색 시간이 필요해 비효율적이다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <ctime>
#define pii pair<int, int>
using namespace std;
constexpr int dr[4] = { 1, -1, 0, 0 };
constexpr int dc[4] = { 0, 0, 1, -1 };
constexpr int MAX = INT_LEAST32_MAX;
int R, C;
int m[1500][1500], tmp[1500][1500], mem[1501];
queue<pii> swan;
vector<pii> ibg;
void init()
{
// make ibg info, marking swan area
queue<pii> i_swan = swan, tq;
deque<pii> ibgs;
int adjoin;
// marking swan area
while (!i_swan.empty())
{
adjoin = 0;
pii pos = i_swan.front();
i_swan.pop();
int swan_num = m[pos.first][pos.second];
for (int d = 0; d < 4; d++)
{
int nr = pos.first + dr[d];
int nc = pos.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || m[nr][nc] == swan_num)
continue;
if (m[nr][nc] == 0)
{
m[nr][nc] = swan_num;
i_swan.push({ nr, nc });
}
else
adjoin = 1;
}
if (adjoin)
tq.push(pos);
}
swan.swap(tq);
for (pii i : ibg)
{
for (int d = 0; d < 4; d++)
{
int nr = i.first + dr[d];
int nc = i.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C)
continue;
if (m[nr][nc] < m[i.first][i.second])
{
ibgs.push_back(i);
}
}
}
for (pii i : ibgs)
{
m[i.first][i.second] = 1;
}
while (!ibgs.empty())
{
pii f = ibgs.front();
int cur = m[f.first][f.second];
ibgs.pop_front();
for (int d = 0; d < 4; d++)
{
int nr = f.first + dr[d];
int nc = f.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || m[nr][nc] <= cur + 1)
continue;
m[nr][nc] = cur + 1;
ibgs.push_back({ nr, nc });
}
}
}
int isPossible(int date) {
queue<pii> tSwan = swan;
if (mem[date])
return mem[date];
mem[date] = -1;
while (!tSwan.empty())
{
pii p = tSwan.front();
tSwan.pop();
int cur = m[p.first][p.second];
for (int d = 0; d < 4; d++)
{
int nr = p.first + dr[d];
int nc = p.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || m[nr][nc] > date || m[nr][nc] == cur)
continue;
if (m[nr][nc] < 0 && m[nr][nc] != cur)
return mem[date] = 1;
tSwan.push({ nr, nc });
m[nr][nc] = cur;
}
}
return mem[date];
}
int solve()
{
int right = R > C ? R : C;
int left = 0, mid;
init();
memcpy(tmp, m, sizeof(tmp));
// left <= right??
while (left < right)
{
memcpy(m, tmp, sizeof(tmp));
mid = (left + right) / 2;
cout << mid << "\n";
if (isPossible(mid) == 1)
right = mid;
else
left = mid + 1;
}
return left;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("in", "r", stdin);
cin >> R >> C;
string tmp;
int cnt = -1;
for (int r = 0; r < R; r++)
{
cin >> tmp;
for (int c = 0; c < C; c++)
{
if (tmp[c] == 'X')
{
m[r][c] = MAX;
ibg.push_back({ r, c });
}
else
{
if (tmp[c] == 'L')
{
m[r][c] = cnt;
cnt -= 1;
swan.push({ r, c });
}
}
}
}
clock_t st, ed;
st = clock();
cout << solve() << "\n";
ed = clock();
cout << "time : " << ed - st << "\n";
return 0;
}
- 좀 더 빠른 풀이(위의 빙산의 녹는 시간을 구하는 시간만큼의 시간이면 충분한 풀이.)
물의 큐 2개, 백조의 큐 2개를 이용한 풀이
- 백조의 큐를 사용하여 백조 영역을 BFS하고 빙산을 만나는 백조 영역을 다음에 순회할 큐에 추가해 준다. 다른 백조 영역을 만나게 되면 현재 날짜를 반환한다.
- 물의 큐를 순회하며 빙산을 만나는 영역을 녹이고, 다음에 순회할 물의 큐에 추가해 준다.
- 날짜를 +1 해준다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#define pii pair<int, int>
using namespace std;
constexpr int dr[4] = { 1, -1, 0, 0 };
constexpr int dc[4] = { 0, 0, 1, -1 };
int R, C;
int m[1500][1500], v[1500][1500];
queue<pii> nwq, wq, nsq, sq;
int solve()
{
int ret = 0;
int adjoin;
while (true)
{
while (!sq.empty())
{
pii f = sq.front();
sq.pop();
int cur = m[f.first][f.second];
adjoin = 0;
for (int d = 0; d < 4; d++)
{
int nr = f.first + dr[d];
int nc = f.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || m[nr][nc] == cur)
continue;
if (!m[nr][nc])
{
adjoin = 1;
continue;
}
if (m[nr][nc] < 0)
return ret;
m[nr][nc] = cur;
sq.push({ nr, nc });
}
if (adjoin)
nsq.push(f);
}
sq.swap(nsq);
while (!wq.empty())
{
pii f = wq.front();
wq.pop();
adjoin = 0;
for (int d = 0; d < 4; d++)
{
int nr = f.first + dr[d];
int nc = f.second + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || v[nr][nc])
continue;
if (!m[nr][nc])
{
nwq.push({ nr, nc });
m[nr][nc] = 1;
}
else
wq.push({ nr, nc });
v[nr][nc] = 1;
}
}
wq.swap(nwq);
ret += 1;
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("in", "r", stdin);
string tmp_str;
cin >> R >> C;
int cnt = -1;
for (int r = 0; r < R; r++)
{
cin >> tmp_str;
for (int c = 0; c < C; c++)
{
if (tmp_str[c] != 'X')
{
wq.push({ r, c });
m[r][c] = 1;
v[r][c] = 1;
if (tmp_str[c] == 'L')
{
sq.push({ r, c });
m[r][c] = cnt;
cnt -= 1;
}
}
}
}
cout << solve() << "\n";
}
댓글남기기