백준 3197. 백조의 호수(C++)
2023. 6. 26. 00:40ㆍ카테고리 없음
입력
- 첫째 줄에 R(행의 수), C(열의 수)가 주어진다. (1 <= R, C <= 1500)
- 다음 R개의 줄에 각각 길이 C의 문자열이 하나씩 주어진다.
- '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간이다.
- 문제의 조건에서 ''백조는 오직 물 공간에서 세로나 가로로만 움직일 수 있다.'라는 문장을 통해 백조가 있는 공간 역시 물 공간이라는 것을 유추할 수 있다.
문제 풀이
- 며칠이 지나야 백조가 존재하는 물 공간(물 공간으로 이어진 전체 공간)이 만날 수 있는지를 구하는 문제이다.
- 첫 접근은 방문했던 공간을 중복해서 방문하지 않는 것에 집중했다.
- 서로 다른 bfs 함수 3개를 만들어 풀이하였다.
- 첫 bfs는 하나의 큰 물 공간을 같은 공간이라고 표시해주는 작업을 했다.
- 두 번째 bfs는 좀 더 빨리 접근할 수 있는 공간 주변을 먼저 탐색하며 얼음 공간을 물 공간으로 바꿔주었다. 우선순위 큐를 사용하여 먼저 접근할 수 있는 공간을 먼저 꺼냈다.
- 세 번째 bfs는 위에서 공간마다 표시한 접근이 가능한 날의 정보를 이용하여 빨리 접근할 수 있는 공간 주변을 먼저 탐색하며 며칠 후에 두 백조가 만날 수 있는지를 도출하였다. 위의 두 번째 bfs와 마찬가지로 우선순위 큐를 사용하였다.
- 아래는 작성한 코드이다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
struct spot {
int num;
int day;
spot() { num = 0; day = 0; }
spot(int a, int b) : num(a), day(b) {}
};
struct cmp {
bool operator () (std::vector<int> x, std::vector<int> y) {
return x[2] > y[2];
}
};
int r, c, result, b1, b2;
std::vector<std::pair<int, int>> goal;
std::vector<std::vector<spot>> lake(1500, std::vector<spot>(1500));
void bfs1(int y, int x, int num) {
std::queue<std::pair<int, int>> q;
q.push(std::make_pair(y, x));
lake[y][x].num = num;
while (!q.empty()) {
int nowy = q.front().first;
int nowx = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = nowy + dy[i];
int nx = nowx + dx[i];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (lake[ny][nx].num == 0) {
lake[ny][nx].num = num;
q.push(std::make_pair(ny, nx));
}
}
}
}
}
void bfs2() {
std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, cmp>q;
for (int i = 0; i<int(goal.size()); i++) {
q.push({ goal[i].first, goal[i].second, 0 });
lake[goal[i].first][goal[i].second].day = 0;
}
while (!q.empty()) {
int nowy = q.top()[0];
int nowx = q.top()[1];
int nowd = q.top()[2];
q.pop();
for (int i = 0; i < 4; i++) {
int ny = nowy + dy[i];
int nx = nowx + dx[i];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (lake[ny][nx].day == -1) {
if (lake[ny][nx].num != -1) {
lake[ny][nx].day = nowd;
}
else if (lake[ny][nx].num == -1) {
lake[ny][nx].day = nowd + 1;
}
q.push({ny, nx, lake[ny][nx].day});
}
}
}
}
}
void bfs3(int y, int x) {
std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, cmp>q;
q.push({ y, x, 0 });
lake[y][x].num = -2;
while (!q.empty()) {
int nowy = q.top()[0];
int nowx = q.top()[1];
int nowd = q.top()[2];
q.pop();
for (int i = 0; i < 4; i++) {
int ny = nowy + dy[i];
int nx = nowx + dx[i];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (lake[ny][nx].num != -2) {
lake[ny][nx].num = -2;
if (lake[ny][nx].day < nowd) {
lake[ny][nx].day = nowd;
}
q.push({ ny, nx, lake[ny][nx].day });
}
if (ny == goal[1].first && nx == goal[1].second) {
return;
}
}
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> r >> c;
int cnt = 1;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
char tmp;
std::cin >> tmp;
if (tmp == 'X') {
spot now = { -1, -1 };
lake[i][j] = now;
}
else if (tmp == '.') {
spot now = { 0, -1 };
lake[i][j] = now;
}
else if (tmp == 'L') {
spot now = { 0, -1 };
lake[i][j] = now;
goal.push_back(std::make_pair(i, j));
cnt += 1;
}
}
}
cnt = 1;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (lake[i][j].num == 0) {
bfs1(i, j, cnt);
cnt += 1;
goal.push_back(std::make_pair(i, j));
}
}
}
bfs2();
bfs3(goal[0].first, goal[0].second);
std::cout << lake[goal[1].first][goal[1].second].day;
return 0;
}
- 생각해보면 당연하게도 시간초과라는 결과가 나왔다.
- bfs를 세 번이나 실행시켰을 뿐더러, 우선순위 큐의 시간복잡도를 전혀 고려하지 않았기 때문이다.
- 따라서 다른 접근이 필요했으며, 큐를 여러개 쓰는 방식을 통해 해결하였다. 1번 백조가 있는 공간에 해당하는 큐 2개, 2번 백조가 있는 공간에 해당하는 큐 2개, 물 공간에 해당하는 큐 2개를 사용하였다.
- 먼저 호수의 정보를 받을 때, 얼음 공간은 -1, 물 공간은 0, 백조가 있는 공간은 각각 1, 2로 변환시켜 2차원 벡터에 저장하였다.
- 먼저 1번 백조 공간에서 bfs를 시작한다. 만약 2번 백조를 만난다면 while문을 종료하고 결과를 도출한다.
- 그리고 물 공간들을 만난다면 현재 사용하고 있는 큐에 삽입을 해준다.
- 얼음 공간을 만난다면 다음 날이 되었을 때 사용할 1번 백조 큐에 삽입을 해준다.
- 후에 2번 백조 공간과 물 공간에서 위와 같은 방식으로 bfs를 한다.
- 위의 사이클이 한번 끝나면 날짜를 하루 늘려준다.
- 아래는 작성한 코드이다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int r, c, nday, flag;
int lake[1500][1500];
int visited[1500][1500];
std::vector<std::queue<std::pair<int, int>>>swan1(2, std::queue<std::pair<int, int>>());
std::vector<std::queue<std::pair<int, int>>>swan2(2, std::queue<std::pair<int, int>>());
std::vector<std::queue<std::pair<int, int>>>water(2, std::queue<std::pair<int, int>>());
//std::queue<std::pair<int, int>>ice;
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
char tmp;
std::cin >> tmp;
if (tmp == 'X') {
lake[i][j] = -1;
}
else if (tmp == '.') {
lake[i][j] = 0;
visited[i][j] = -1;
water[nday%2].push(std::make_pair(i, j));
}
else {
lake[i][j] = flag + 1;
if (flag == 0) {
swan1[nday%2].push(std::make_pair(i, j));
}
else {
swan2[nday%2].push(std::make_pair(i, j));
}
visited[i][j] = 1;
flag += 1;
}
}
}
flag = 0;
while (1) {
while (!swan1[nday%2].empty()) {
int nowy = swan1[nday%2].front().first;
int nowx = swan1[nday%2].front().second;
swan1[nday%2].pop();
for (int i = 0; i < 4; i++) {
int ny = nowy + dy[i];
int nx = nowx + dx[i];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (lake[ny][nx] == 2) {
flag = 1;
break;
}
if (visited[ny][nx] != 1) {
visited[ny][nx] = 1;
if (lake[ny][nx] == 0) {
lake[ny][nx] = 1;
swan1[nday%2].push(std::make_pair(ny, nx));
}
else if (lake[ny][nx] == -1) {
lake[ny][nx] = 1;
swan1[(nday + 1) % 2].push(std::make_pair(ny, nx));
}
}
}
}
}
if (flag == 1) {
break;
}
while (!swan2[nday % 2].empty()) {
int nowy = swan2[nday % 2].front().first;
int nowx = swan2[nday % 2].front().second;
swan2[nday % 2].pop();
for (int i = 0; i < 4; i++) {
int ny = nowy + dy[i];
int nx = nowx + dx[i];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (visited[ny][nx] != 1) {
visited[ny][nx] = 1;
if (lake[ny][nx] == 0) {
lake[ny][nx] = 2;
swan2[nday % 2].push(std::make_pair(ny, nx));
}
else if (lake[ny][nx] == -1) {
lake[ny][nx] = 2;
swan2[(nday + 1) % 2].push(std::make_pair(ny, nx));
}
}
}
}
}
while (!water[nday%2].empty()) {
int nowy = water[nday%2].front().first;
int nowx = water[nday%2].front().second;
water[nday%2].pop();
if (visited[nowy][nowx] == 1) {
continue;
}
visited[nowy][nowx] = -1;
for (int i = 0; i < 4; i++) {
int ny = nowy + dy[i];
int nx = nowx + dx[i];
if (0 <= ny && ny < r && 0 <= nx && nx < c) {
if (visited[ny][nx] == 1) {
continue;
}
if (visited[ny][nx] != -1) {
visited[ny][nx] = -1;
if (lake[ny][nx] == -1) {
lake[ny][nx] = 0;
water[(nday + 1) % 2].push(std::make_pair(ny, nx));
}
}
}
}
}
nday++;
}
std::cout << nday;
return 0;
}
