백조의 호수

코드

[ 실패 코드(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] 입력 받으면서 L or .이면 빙하를 녹일 수 있으므로 W 큐에 삽입
  • 백조가 오늘 갈 수 있는 곳은 L 큐를 통해 계속 돌면서 백조(L)가 있는지검사
    & 빙하로 막혀 다음날 갈 수 있는 곳은 nextQ 큐에 삽입
  • 현재 W 큐에 있는 만큼만 돌면서 접해있는 빙하를 모두 물로 변환 (X -> .)
  • 앞의 과정을 반복!
    (출처 : https://rile1036.tistory.com/115)

• 시간 단축
  • 이전 : 빙하를 녹이는 과정에 대해 2중 반복문으로 시행함 --> 무조건 O(N^2)
  • 지금 : 빙하를 녹이는 과정에 대해 최초에만 모든 물에 대해 실행 & 나머지는 물이 된 빙하에 대해서만 실행
    (이전 경우보다 수가 많이 줄어든다)
    (추가적으로, 백조가 이동하는 과정도 다음날 갈 수 있는 좌표를 구하므로 이전날 갔던 좌표에 대한 중복 검사가 사라짐! --> 시간 단축)

• 느낀 점
  • 꼭 필요한 부분만 탐색하기 위한 BFS를 하면 시간이 단축됨
  • 백조의 이동 / 빙하 녹음 이 2가지 행위가 필요함 --> 2개의 BFS가 필요!
    2개 BFS를 따로 하는 경우를 생각해보자