-
백조의 호수문제
사실 여태까지 문제를 풀면서 재귀를 쓰는게 아니고서야, 메모리초과나 스택오버플로우를 걱정해본적은없는데,
이건 코드짜면짤수록 메모리가 엄청나게 신경쓰였다.
또한 문제를 잘읽어야하는 이유중의 한가지는 바로 백조가있는곳 역시 물이기때문에 이곳과 접촉해있는 얼음도 녹는다는것이다. 혹시나 논증의 여지가있다면, 문제 어디에도 백조가 절대로 다른백조를 만나지 못한다는 조건이 없다는것이다.
인접한 물이녹는다거나 이런류의 문제를 보면 딱떠오르는게 BFS인데,
초기로직은 다음과같다
#include<cstdio> #include<iostream> #include<vector> #include<cstring> #include<cstdlib> #include<queue> #include<utility> using namespace std; int r, c; int map[1500][1500]; bool d[1500][1500]; bool go[1500][1500]; bool noG = false; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; bool con = false; vector<pair<int, int>>v; vector<pair<int, int>> vv; void bfs() { queue < pair<int, int>> q; for (int i = 0; i < v.size(); i++) { q.push(v[i]); d[v[i].first][v[i].second] = true; } v.clear(); if (q.empty()) { noG = true; return; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if (map[nx][ny] == 2 && d[nx][ny] == false) { map[nx][ny] = 0; d[nx][ny] = true; v.push_back({ nx,ny }); } } } } } void bfsL() { queue<pair<int, int>> q; q.push(vv[0]); go[vv[0].first][vv[0].second] = true; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if ((map[nx][ny] == 0)&& go[nx][ny] == false) { go[nx][ny] = true; q.push({ nx,ny }); if (nx == vv[1].first && ny == vv[1].second) { con = true; return; } } } } } } int main() { cin >> r >> c; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { char x; cin >> x; if (x == '.') { map[i][j] = 0; v.push_back({ i,j }); } if (x == 'X') map[i][j] = 2; if (x == 'L') { map[i][j] = 0; v.push_back({ i,j }); vv.push_back({ i,j }); } } } int i = 0; while (true) { memset(go, 0, sizeof(go)); bfsL(); if (con) break; i++; bfs(); } cout << i << endl; return 0; }얼음이 녹는 BFS하나, 그리고 백조하나가 움직여서 다른백조까지가는 BFS하나를 써서 문제를 풀어보았다.
하지만, 역시나 시간초과가났는데, 내 예상에 시간초과의 가장큰원인은 얼음이 녹고나서,
백조가 "처음부터 다시 BFS" 를 하는 과정이라고 생각했고 학원끝나고 집에 와서 해당부분을 고려해 문제를다시풀었다.
#include<cstdio> #include<iostream> #include<vector> #include<cstring> #include<cstdlib> #include<queue> #include<utility> using namespace std; int r, c; int map[1500][1500]; bool d[1500][1500]; bool go[1500][1500]; bool noG = false; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; bool con = false; vector<pair<int, int>>v; vector<pair<int, int>> vv; pair<int, int> pairing; void bfs() { queue < pair<int, int>> q; for (int i = 0; i < v.size(); i++) { q.push(v[i]); d[v[i].first][v[i].second] = true; } v.clear(); if (q.empty()) { noG = true; return; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if (map[nx][ny] == 2 && d[nx][ny] == false) { map[nx][ny] = 0; d[nx][ny] = true; v.push_back({ nx,ny }); } } } } } void bfsL() { queue<pair<int, int>> q; for (int i = 0; i < vv.size(); i++) { q.push(vv[i]); go[vv[i].first][vv[i].second] = true; } vv.clear(); while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if (map[nx][ny] == 2) { vv.push_back({ nx,ny }); } if ((map[nx][ny] == 0) && go[nx][ny] == false) { go[nx][ny] = true; q.push({ nx,ny }); if (nx == pairing.first && ny == pairing.second) { con = true; return; } } } } } } int main() { cin >> r >> c; bool next = false; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { char x; cin >> x; if (x == '.') { map[i][j] = 0; v.push_back({ i,j }); } if (x == 'X') map[i][j] = 2; if (x == 'L') { map[i][j] = 0; v.push_back({ i,j }); if (next == false) { vv.push_back({ i,j }); next = true; } if (next == true) { pairing.first = i; pairing.second = j; } } } } int i = 0; while (true) { bfsL(); if (con) break; i++; bfs(); } cout << i << endl; return 0; }이번엔 메모리 초과가 났다. 아무래도 다음에 녹아버릴 얼음을 다음에 움직일 방향으로 판단하고 vv벡터에넣는과정에서
중복으로 체크하는 기능이 없어서, 많으면 4번 적게는 1번의 중복이 발생했을거라생각하고, 그양이 [1500][1500] 이라면
공간복잡도가 상당히 클것이라 생각한다. 따라서 해당부분을 제거하기 위해 bool 배열을 하나더만들어서 사용했다.
#include<cstdio> #include<iostream> #include<vector> #include<cstring> #include<cstdlib> #include<queue> #include<utility> using namespace std; int r, c; int map[1500][1500]; bool d[1500][1500]; bool go[1500][1500]; bool hext[1500][1500]; bool noG = false; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; bool con = false; vector<pair<int, int>>v; vector<pair<int, int>> vv; pair<int, int> pairing; void bfs() { queue < pair<int, int>> q; for (int i = 0; i < v.size(); i++) { q.push(v[i]); d[v[i].first][v[i].second] = true; } v.clear(); if (q.empty()) { noG = true; return; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if (map[nx][ny] == 2 && d[nx][ny] == false) { map[nx][ny] = 0; d[nx][ny] = true; v.push_back({ nx,ny }); } } } } } void bfsL() { queue<pair<int, int>> q; for (int i = 0; i < vv.size(); i++) { q.push(vv[i]); go[vv[i].first][vv[i].second] = true; } vv.clear(); while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if (map[nx][ny] == 2 && hext[nx][ny] == false) { vv.push_back({ nx,ny }); hext[nx][ny] = true; } if ((map[nx][ny] == 0) && go[nx][ny] == false) { go[nx][ny] = true; q.push({ nx,ny }); if (nx == pairing.first && ny == pairing.second) { con = true; return; } } } } } } int main() { cin >> r >> c; bool next = false; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { char x; cin >> x; if (x == '.') { map[i][j] = 0; v.push_back({ i,j }); } if (x == 'X') map[i][j] = 2; if (x == 'L') { map[i][j] = 0; v.push_back({ i,j }); if (next == false) { vv.push_back({ i,j }); next = true; } if (next == true) { pairing.first = i; pairing.second = j; } } } } int i = 0; while (true) { bfsL(); if (con) break; i++; bfs(); } cout << i << endl; return 0; }아래와같이 짯고, 결과는 역시 성공적이다.
음.. 아마 시간복잡도를 조금더 줄여낼수있는방법이 떠오를거같은데 피곤해서 일단 여기까지만해보자.