백준 3197, 백조의 호수
문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다. 며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다(단, 1 ≤ R, C ≤ 1500). 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
예제 입력
4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...예제 출력
2출처 : https://www.acmicpc.net/problem/3197
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
그래프에 관한 문제를 다루어 보는 것은 이번이 처음이여서 오래 푸는 데 오래 걸렸던 문제이다. 간단하게 정리하자면 BFS를 효율적으로 수행할 수 있느냐에 관한 문제였다. 여기서 중요한 것은 "효율적"이어야 한다는 것이다. 최대한 중복을 피해야 한다는 것인데 이 점을 관과하여 처음에는 시간 초과로 문제를 틀렸다. 처음 내가 생각한 풀이 방식은 다음과 같았다.
- 백조 하나의 위치를 중심으로 BFS를 실행한다.
- 만약 다른 백조를 찾았다면 지금까지 지난 시간을 반환한다.
- 만약 다른 백조를 찾지 못하였다면, 맵을 순회하면서 물 근처에 있는 얼음들을 녹여주는 작업을 한다.
- 백조를 찾을 때까지 1~3 과정을 반복한다.
계속 시간 초과가 일어나서, 이 문제를 해결하기 위해 BFS 후 맵을 초기화하는 과정이나, 순회하면서 얼음을 녹이는 과정을 보다 효율적으로 만들고자 하였다. 결과적으로는 시간 초과 문제를 해결하지는 못하였다. 가장 본질적인 시간 초과의 원인은 처음을 제외하고 굳이 BFS의 시작 시점을 백조의 위치로 잡을 필요가 없다는 것이였다. 이 부분을 손 보지 않았으니 당연히 시간 초과가 나올 수 밖에 없었다. 일단은 내가 썼던 코드를 올려 본다.
#include <iostream>
#include <string>
#include <sstream>
#include <queue>
#include <algorithm>
#include <vector>
struct Plane {
char type;
bool visited;
};
int R, C;
Plane plane[1501][1501] = { {{'X', false}, }, };
std::pair<int, int> goose[2];
std::pair<int, int> movement[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, }; // 0 = right, 1 = left, 2 = down, 3 = up
std::vector<std::pair<int, int>> ice;
//whether geese meet each other
bool whetherGeeseMeet() {
std::queue<std::pair<int, int>> passed;
plane[goose[0].first][goose[0].second].visited = true;
passed.push(goose[0]);
std::pair<int, int> next;
while (!passed.empty()) {
std::pair<int, int> now = passed.front();
passed.pop();
for (int i = 0; i < 4; i++) {
next = { now.first + movement[i].first, now.second + movement[i].second };
if (plane[next.first][next.second].type == 'L') {
if (!plane[next.first][next.second].visited) {
return true;
}
}
else if (plane[next.first][next.second].type == '.') {
if (!plane[next.first][next.second].visited) {
plane[next.first][next.second].visited = true;
passed.push(next);
}
}
}
}
for (int i = 1; i < R+1; i++) {
for (int j = 1; j < C+1; j++) {
plane[i][j].visited = false;
}
}
return false;
}
//ice melting
void dayPassed() {
if (ice.empty())
return;
std::queue<std::pair<int, int>> willBeMelted;
std::pair<int, int> around;
for (int i = 0; i < ice.size();) {
bool plus = true;
for (int k = 0; k < 4; k++) {
around = { ice[i].first + movement[k].first, ice[i].second + movement[k].second };
if (plane[around.first][around.second].type == '.') {
willBeMelted.push(ice[i]);
ice.erase(ice.begin() + i);
plus = false;
break;
}
}
if (plus) {
i++;
}
}
while (!willBeMelted.empty()) {
std::pair<int, int> toBeMelted = willBeMelted.front();
plane[toBeMelted.first][toBeMelted.second].type = '.';
willBeMelted.pop();
}
}
int main() {
std::cin >> R >> C;
std::cin.ignore();
std::string str;
std::stringstream ss;
char input;
int numOfgoose = 0;
for (int i = 1; i < R+1; i++) {
std::getline(std::cin, str);
ss << str;
for (int j = 1; j < C+1; j++) {
ss >> input;
if (input == 'L') {
goose[numOfgoose] = { i, j };
numOfgoose++;
}
else if (input == 'X') {
ice.push_back({i, j});
}
plane[i][j].type = input;
plane[i][j].visited = false;
}
ss.clear();
str.clear();
}
//code here
int day = 0;
while (!whetherGeeseMeet()) {
dayPassed();
day++;
}
std::cout << day;
return 0;
}다음은 인터넷에서 찾은 답이다.(틀린 부분은 알았는데 코드가 훨씬 간결해서 그냥 따라적는 것으로 오답 풀이를 대체 했다.) 차이점은, 처음을 제외하고는 BFS의 시작 지점이 전 탐색 과정에서 찾았던 얼음들이라는 것이다. 굳이 왔던 길에 대해서 탐색할 필요가 없다는 뜻이다. 그 외에는 알고리즘 상에서의 큰 차이가 없던 것 같다.
#include <vector>
#include <iostream>
#include <string>
#include <queue>
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };
using namespace std;
int R, C;
string arr[1501];
bool visited[1501][1501];
vector<pair<int, int>> target;
queue<pair<int, int>> v;
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> arr[i];
for (int j = 0; j < C; j++) {
if (arr[i][j] == 'L') {
target.push_back({ j, i });
arr[i][j] = '.';
v.push({ j, i });
}
else if (arr[i][j] == '.') v.push({ j, i });
}
}
queue<pair<int, int>> q;
int ans = 0;
q.push(target[0]);
visited[target[0].second][target[0].first] = true;
while (true) {
queue<pair<int, int>> next;
while (!q.empty()) {
int r = q.front().second;
int c = q.front().first;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + c;
int ny = dy[i] + r;
if (nx < 0 || ny < 0 || nx >= C || ny >= R || visited[ny][nx]) continue;
else if (target[1] == make_pair(nx, ny)) {
cout << ans;
return 0;
}
else if (arr[ny][nx] == 'X') next.push({ nx, ny });
else q.push({ nx ,ny });
visited[ny][nx] = true;
}
}
q = next;
ans++;
int n = v.size();
while (n--) {
int r = v.front().second;
int c = v.front().first;
v.pop();
for (int j = 0; j < 4; j++) {
int nx = dx[j] + c;
int ny = dy[j] + r;
if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
else if (arr[ny][nx] == 'X') {
v.push({ nx, ny });
arr[ny][nx] = '.';
}
}
}
}
return 0;
}
//출처 : https://velog.io/@asdsa2134그래프에 대해서 처음 다루었던 만큼 시간이 오래 걸린 것 같다. 무작정 정형화된 알고리즘을 그대로 사용하기보다는 어떻게 하면 조금 더 효율적으로 알고리즘을 활용할 수 있는지를 생각하는 것이 중요하다는 것을 느꼈다. 그 중에서도 반복을 어떻게 줄일 것인가에 대해 고민하는 것은 상당히 중요한 문제임을 알 수 있었다. 이 것으로 글을 마친다.