백조의 호수
코드
[ 실패 코드(1) ] - 직관적 풀이
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define INF 1e9 using namespace std; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; char board[1501][1501]; char board2[1501][1501]; int R, C, ans; vector<pair<int,int>> L; // 빙하녹기(BFS) -> 검사하기(BFS) void melt() { for(int i=0;i<R;i++) for(int j=0;j<C;j++) board2[i][j] = board[i][j]; for(int i=0;i<R;i++) { for(int j=0;j<C;j++) { if(board[i][j] != 'X') continue; bool flag = false; for(int dir=0;dir<4;dir++) { int ny = i + dy[dir]; int nx = j + dx[dir]; if(nx<0 or ny<0 or nx>=C or ny>=R) continue; if(board[ny][nx] == 'X') continue; flag = true; break; } if(flag) board2[i][j] = '.'; } } for(int i=0;i<R;i++) for(int j=0;j<C;j++) board[i][j] = board2[i][j]; } bool check() { queue<pair<int,int>> q; bool vis[R][C]; for(int i=0;i<R;i++) fill(vis[i], vis[i]+C, false); vis[L[0].first][L[0].second] = true; q.push(L[0]); while(!q.empty()) { auto cur = q.front(); q.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=C or ny>=R) continue; if(vis[ny][nx] or board[ny][nx] == 'X') continue; q.push({ny, nx}); vis[ny][nx] = true; if(board[ny][nx] == 'L') return true; } } return false; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> R >> C; for(int i=0;i<R;i++) for(int j=0;j<C;j++) { cin >> board[i][j]; if(board[i][j] == 'L') L.push_back({i,j}); } while(true) { if(check()) break; melt(); ans++; } cout << ans; return 0; }
- 로직
BFS로 현재L --> L가능한지 검사BFS로 물에 인접한빙하 녹이기
- 결과
: 시간초과! (해당 문제는O(N^2)까지 허용)
- 시간 복잡도
check()-->O(N^2)melt()-->O(N^2)- 최악의 경우에 가장
대각선에백조(L)가 있고나머지 다 빙하일 때O(N)만큼 while문 실행- 총 :
O(N^3)
[ 실패 코드(2) ] - 3차원 cost 계산
#include <iostream> #include <vector> #include <queue> #include <cmath> #define INF 1e9 using namespace std; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; char board[1501][1501]; int cost[1501][1501][1501]; // 1500*1500*1500*4 byte = 13.5GB! int R, C, ans=INF; vector<pair<int,int>> L; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> R >> C; int B = max(R,C)+1; for(int i=0;i<R;i++) for(int j=0;j<C;j++) { cin >> board[i][j]; if(board[i][j] == 'L') L.push_back({i,j}); } for(int i=0;i<B;i++) for(int j=0;j<R;j++) for(int k=0;k<C;k++) cost[i][j][k] = INF; for(int i=0;i<B;i++) cost[i][L[0].first][L[0].second] = 0; queue<pair<pair<int,int>,int>> q; q.push({{L[0]},0}); while(!q.empty()) { auto cur = q.front(); q.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first.first + dy[dir]; int nx = cur.first.second + dx[dir]; int status = cur.second; if(nx<0 or ny<0 or nx>=C or ny>=R) continue; if(board[ny][nx] == 'X') status++; if(cost[status][ny][nx] <= cost[cur.second][cur.first.first][cur.first.second] + 1) continue; q.push({{ny, nx},status}); cost[status][ny][nx] = cost[cur.second][cur.first.first][cur.first.second] + 1; } } for(int i=0;i<B;i++) { if(cost[i][L[1].first][L[1].second] == INF) continue; ans = i; break; } ans = ceil(ans/2.0); cout << ans; return 0; }
- 실패 이유
- 시간 초과 :
cost[][][]배열을INF로 초기화 하려면 어차피O(N^3)걸림for(int i=0;i<B;i++) for(int j=0;j<R;j++) for(int k=0;k<C;k++) cost[i][j][k] = INF;
- 메모리 초과
:int cost[1501][1501][1501]의 크기는1500*1500*1500*4byte=13.5GB!
- 느낀 점
: 3차원 cost방식(cost[status][N][M])은입력의 수가 작고&status가 N이 아닐 때
O(N^3)-->O(N^2)로 할 수 있음
[ 정답 풀이 ]
#include <iostream> #include <vector> #include <queue> #include <cmath> #define INF 1e9 using namespace std; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; char board[1501][1501]; bool vis[1501][1501]; int R, C, day; queue<pair<int,int>> L; // 백조가 움직이는 큐 queue<pair<int,int>> W; // 빙하를 녹이기 위는 큐 vector<pair<int,int>> l; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> R >> C; for(int i=0;i<R;i++) for(int j=0;j<C;j++) { cin >> board[i][j]; if(board[i][j] == 'L') l.push_back({i,j}); if(board[i][j] == '.' or board[i][j] == 'L') W.push({i,j}); } L.push(l[0]); vis[l[0].first][l[0].second] = true; bool flag = false; while(true) { queue<pair<int,int>> nextQ; /* 다음날 백조가 움직일 수 있는 좌표를 큐 */ while(!L.empty()) { auto cur = L.front(); L.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=C or ny>=R) continue; if(vis[ny][nx]) continue; /* board에 따라 다음날에 갈수있는 곳인지, 오늘 갈수있는곳인지 다름 */ if(board[ny][nx] == 'X') nextQ.push({ny,nx}); else L.push({ny, nx}); vis[ny][nx] = true; // 방문처리는 모두 다 해줘야 함 if(ny == l[1].first and nx == l[1].second) { flag=true; goto stop; } } } stop: if(flag) break; L = nextQ; int WSize = W.size(); /* 현재 모든 물에 인정한 빙하를 녹이는 큐 --> 빙하를 녹이는 과정을 `2중 반복문`이 아닌 `현재 물의 위치로 BFS 하는 것`이 더 빠름! 2중 반복문 : O(N^2) BFS : 최초 실행시에만 물의 전체 개수만큼, 나머지는 인접한 개수만큼 BFS 실행 */ while(WSize--) { auto cur = W.front(); W.pop(); for(int dir=0;dir<4;dir++) { int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(nx<0 or ny<0 or nx>=C or ny>=R) continue; if(board[ny][nx] != 'X') continue; W.push({ny, nx}); board[ny][nx] = '.'; } } day++; } cout << day; return 0; }
- 로직
board[R][C]입력 받으면서Lor.이면 빙하를 녹일 수 있으므로W 큐에 삽입- 백조가 오늘 갈 수 있는 곳은
L 큐를 통해 계속 돌면서백조(L)가 있는지검사
& 빙하로 막혀 다음날 갈 수 있는 곳은nextQ 큐에 삽입- 현재
W 큐에 있는 만큼만 돌면서접해있는 빙하를 모두물로 변환 (X->.)- 앞의 과정을 반복!
(출처 : https://rile1036.tistory.com/115)
- 시간 단축
- 이전 :
빙하를 녹이는 과정에 대해2중 반복문으로 시행함 --> 무조건O(N^2)- 지금 :
빙하를 녹이는 과정에 대해 최초에만 모든 물에 대해 실행 & 나머지는 물이 된 빙하에 대해서만 실행
(이전 경우보다수가 많이줄어든다)
(추가적으로,백조가 이동하는 과정도다음날 갈 수 있는 좌표를 구하므로이전날 갔던 좌표에 대한중복 검사가 사라짐! -->시간 단축)
- 느낀 점
꼭 필요한 부분만탐색하기 위한BFS를 하면시간이 단축됨백조의 이동/빙하 녹음이2가지 행위가 필요함 -->2개의 BFS가 필요!
2개 BFS를따로 하는 경우를 생각해보자
Developer & PhotoGrapher