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

[문제보기]

 

[해결과정]

 

 1. 입력 받기 (n, m , arr[][])

   -> 백조 구조체를 생성하여, 0번 백조 1번 백조 입력 받기.

   -> 물일 경우 ( . ) wq(큐)에 넣기

 

 2. q(큐)에 0번 백조 좌표 넣기

 3. 결과를 도출할 날짜 ans =0으로 셋팅 후 무한 반복문 실행

 

 4. nq( q와 동일한 큐 )생성

 5. 0번 백조 돌리기 (q를 다 돌때까지)

   -> 만약 X라면 nq에 좌표 넣기

   -> 만약 X가 아니라면 q에 좌표 넣기

   ★★★0번 백조가 돌아다닐 수 있는 범위를 탐색하는 것임!

 

 6. q에 nq를 넣기

 

 7. 얼음 부수기

   -> int s 에 wq.size() 값 대입

   -> while(s--) 반복문 BFS 실행

   -> 만약 X라면 wq에 좌표 넣고 해당 좌표 값을 '.'으로 변경

   

 ★★★ 여기서 얼음들이 제대로 부숴지는지 디버깅 해볼 것!!!

 

 8. ans 출력

 

[소스코드]

/*
    BOJ 3197 - 백조의 호수
    Created by haejun on 2020/02/26
*/
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX = 1502;
 
int n, m;
char arr[MAX][MAX];
bool check[MAX][MAX];
 
struct coor {
    int y;
    int x;
};
 
// 백조
coor duck[2];
 
//0번 백조에 대한 큐, 물에 대한 큐
queue<coor> q; queue <coor> wq;
 
//inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    int now = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'L') {
                duck[now].y = i;
                duck[now].x = j;
                now++;
                wq.push({ i,j });
            }
            else if (arr[i][j] == '.') {
                wq.push({ i,j });
            }
        }
    }
 
    q.push({ duck[0].y, duck[0].x });
 
    int ans = 0;
    while (1) {
        bool flag = false;
        queue<coor> nq;
        //0번 백조 돌기.
        while (!q.empty()) {
            int y = q.front().y;
            int x = q.front().x;
            q.pop();
 
            if (y == duck[1].y && x == duck[1].x) {
                flag = true;
                break;
            }
 
            int ny, nx;
            for (int i = 0; i < 4; i++) {
                ny = y + dy[i];
                nx = x + dx[i];
                if (inside(ny, nx) && check[ny][nx] == 0 && arr[ny][nx] != 'X') {
                    q.push({ ny,nx });
                    check[ny][nx] = 1;
                }
                else if (inside(ny, nx) && check[ny][nx] == 0 && arr[ny][nx] == 'X') {
                    nq.push({ ny,nx });
                    check[ny][nx] = 1;
                }
            }
            if (flag == true) break;
        }
 
        if (flag == true) break;
 
        q = nq;
 
        // 얼음 뿌수기
        int s = wq.size();
        while (s--) {
            int y = wq.front().y;
            int x = wq.front().x;
            wq.pop();
 
            int ny, nx;
            for (int i = 0; i < 4; i++) {
                ny = y + dy[i];
                nx = x + dx[i];
                if (inside(ny, nx) && arr[ny][nx] == 'X') {
                    wq.push({ ny,nx });
                    arr[ny][nx] = '.';
                }
            }
        }
 
        //디버깅
        /*
        cout << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        */
 
        ans++;
    }
    cout << ans << "\n";
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 단순한 BFS로 생각하면 1500 * 1500 이기 때문에, 시간과 메모리에서 터져버린다. 처음에는 두 백조에 대해서 모두 탐색을 실시했는데, 그럴 필요없이 한개의 백조만 돌아보면 되기때문에, 전에 방법보다 두배 시간이 줄어든다.

 

 그리고 모든 맵을 돌며 .을 큐에 넣고 bfs를 돌며 X를 한개씩 깍아나갔는데, 그럴경우 맵을 계속 돌아야하고, 시간적으로 비효율적이다. 그래서 다음에 부숴질 X좌표를 미리 가지고 있다가 그 좌표에 대해서 bfs를 하며 한 단계씩 나아가는 것으로 해결했다.

 

 조금 난해한 문제였고 생각이 필요한 문제였다.. 코딩테스트에 나올만한 문제인 것 같다. 골드2 레벨이기도 하고... 한동안 못풀었다가 이번에 풀었다!

 

 

[관련 문제 혹은 비슷한 문제]

 BFS