3197번-백조의 호수 (어려움)

참고한 글

---

https://yabmoons.tistory.com/64

[ 백준 3197 ] 백조의 호수 (C++)

 

중요 지식

---

BFS - 백조가 어디있는지 알아낸다.

queue - 물을 넣는다.

코드

---

#include <iostream> 
#include <vector> 
#include <string> 
#include <queue> 

using namespace std; 

const int MAX = 1500; 
typedef struct { 
    int y, x; 
} Dir; 
Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; 
int R, C; string lake[MAX]; 

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;

    vector<pair<int, int>> swan;
    queue<pair<int, int>> waterQ;

    for (int i = 0; i < R; i++)
    {
        cin >> lake[i];
        for (int j = 0; j < C; j++)
        {
            if (lake[i][j] == 'L')
            {
                swan.push_back({i, j});
            }
            if (lake[i][j] == '.' || lake[i][j] == 'L')
            {
                waterQ.push({i, j});
            }
        }
    }

    queue<pair<int, int>> q;
    q.push(swan[0]);

    bool visited[MAX][MAX] = { false, };
    visited[swan[0].first][swan[0].second] = true;

    int day = 0;
    while (1)
    {
        queue<pair<int, int>> nextQ;
        bool flag = false;

        while (!q.empty())
        {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();

            if (y == swan[1].first && x == swan[1].second) {
                flag = true;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nextY = y + moveDir[i].y;
                int nextX = x + moveDir[i].x;

                if (nextY < 0 || nextY >= R || nextX < 0 || nextX >= C || visited[nextY][nextX])
                    continue;

                visited[nextY][nextX] = true; // 물에 인접한 얼음이므로 다음 날에 백조가 탐색할 곳이므로 nextQ에 넣어준다

                if (lake[nextY][nextX] == 'X') {
                    nextQ.push({nextY, nextX});
                    continue;
                }

                q.push({nextY, nextX});
            }
        }

        if (flag)
            break;

        q = nextQ; // 얼음을 녹이는 과정

        int waterQSize = waterQ.size();
        while (waterQSize--) {
            int y = waterQ.front().first;
            int x = waterQ.front().second;
            waterQ.pop();

            for (int i = 0; i < 4; i++) {
                int nextY = y + moveDir[i].y;
                int nextX = x + moveDir[i].x;

                if (nextY < 0 || nextY >= R || nextX < 0 || nextX >= C) {
                    continue;
                }

                if (lake[nextY][nextX] == 'X') {
                    lake[nextY][nextX] = '.';
                    waterQ.push({nextY, nextX});
                }
            }
        }
        
        day++;
    }
    cout << day << "\n";
    return 0;
}

풀이

---

궁금한 것이 한두가지가 아니라 차근차근 알아내보자

 

Q. bfs를 사용한 이유

A.

 

Q. waterQ의 의미

A.

 

아래는 직접 쓴 실패한 코드이다

탐색 알고리즘이라곤 아는게 DFS와 BFS이고 백트래킹은 쓸 수 없을거 같아 DFS만으로 썼다 하지만 시간초과로 실패했다

 

#include <iostream>

using namespace std;

int R, C;
char map[1501][1501];
int v[1501][1501];
int duckV[1501][1501];
int dx, dy;
int duckCount = 0;


int rd[4] = {0, 1, 0, -1};
int cd[4] = {1, 0, -1, 0};

void initDuckV(){
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            duckV[i][j] = 0;
        }
    }
}

void initV(){
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            v[i][j] = 0;
        }
    }
}

void nextDay(int r, int c){    
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(map[i][j] == 'X') v[i][j] = 1;   // 빙하 체크

            for(int k = 0; k < 4; k++){
                int x = i + rd[k];
                int y = j + cd[k];

                if((x < 0 || x >= R) || (y < 0 || y >= C)) 
                    continue;

                if(map[i][j] == 'X' && map[x][y] == '.' && v[x][y] != 1) // 자신이 빙하이고, 주위에 물이 있다해도 오늘 물로 변한 빙하엔 상호작용하지 않는다
                    map[i][j]  = '.';
            }
        }
    }
}

void duckDFS(int r, int c){
    if(duckV[r][c] || map[r][c] == 'X') return;

    duckV[r][c] = 1;
    if(map[r][c] == 'L') duckCount++;

    for(int i = 0; i < 4; i++){
        int x = r + rd[i];
        int y = c + cd[i];

        if((x < 0 || x >= R) || (y < 0 || y >= C)) 
            continue;

        duckDFS(x, y);
    }
}

void printMap(){
    printf("\n 맵 출력=======================\n");

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            printf("%c ", map[i][j]);

            if(map[i][j] == 'L'){
                dx = i;
                dy = j;
            }
        }
        printf("\n");
    }
}

int main(){
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    int day = 0;

    cin >> R >> C;

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> map[i][j];
        }
    }

    duckDFS(dx, dy);
    while(duckCount != 2){
        day++;
        duckCount = 0;
        initV();
        initDuckV();

        nextDay(0, 0);
        // printMap(); 간편 디버깅 

        duckDFS(dx, dy);
    }

    cout << day;

    return 0;
}