[baekjoon] 3197번 : 백조의 호수 (C++)

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

이건 BFS 문제이다

BFS (Breath-First search)

- L과 L 사이에 경로가 존재하는지 판별하고, 경로가 없다면 하루가 지나 얼음이 녹은 상태에서 다시 탐색

- 반복문을 통해 길을 찾을때까지 반복한다면 시간초과

 

BFS는?

1. L(시작노드) 방문

- 방문한 노드 큐에 삽입

2. 큐에서 꺼낸 노드와 인접한 노드를 차례로 방문

- 큐에서 꺼낸 노드 방문(인접한 노드가 없다면 큐의 front에서 노드 꺼냄)

- 큐에 방문한 노드 삽입

3. 큐가 소진될 때까지 계속

 

이걸 이 문제에 적용한다면

1. 먼저 둘 중 하나의 L 주변에 있는 물을 BFS로 탐색

2. 다른 L을 찾을 수 없었다면 물 옆의 얼음을 nextQ에 삽입

3. 얼음을 녹임(하루 지남)

4. 그렇다면 nextQ에는 L이 둘러볼 물이 남음(이전에 탐색한 물을 재탐색할 필요 X)

- waterQ를 생성해 물을 저장해놓고, 얼음을 녹이는 방식도 있음

 

[코드]

// BOJ 3197번 : 백조의 호수
#include <iostream>
#include <queue>
using namespace std;

struct Queue{ // 좌표 2개로 이루어진 큐
    int x;
    int y;
};

char lake[1501][1501]; // 호수
char visit[1501][1501]; // 방문 표시 배열
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
    int r, c; // 호수의 행, 열
    int lr, lc; // L의 위치
    string s; // 호수 받기
    int day = 0; // 걸리는 날

    queue<Queue> waterQ; // 물인 곳을 넣는 큐
    cin >> r >> c; // 먼저 행과 열을 입력받음

    for(int i = 0; i < r; i++){
        cin >> s; // 문자열 입력받음(줄 단위)
        for(int j = 0; j < c; j++){
            lake[i][j] = s[j]; // 입력받은 문자를 호수 배열에 대입
            if(lake[i][j] == 'L'){ // 만약 L이라면
                lr = i; // L의 위치를 저장
                lc = j;
            }
            if(lake[i][j] == '.' || lake[i][j] == 'L'){
                waterQ.push({i, j}); // 물이라면 waterQ에 push
            }
        }
    }

    queue<Queue> Q;
    Q.push({lr, lc}); // L의 위치를 push
    visit[lr][lc] = true; // L의 위치 방문했다고 체크

    while(1){
        queue<Queue> nextQ;
        bool success = false;
        while(!Q.empty() && !success){ // 큐가 비어있지 않고, 성공하지 않을경우 반복
            auto temp = Q.front();
            Q.pop();

            for(int i = 0; i < 4; i++){ // 현재 위치에서 주위 탐색하는 것(상하좌우)
                int nx = temp.x + dx[i]; // 다음 탐색할 x
                int ny = temp.y + dy[i]; // 다음 탐색할 y

                if(nx < 0 || nx > r - 1 || ny < 0 || ny > c - 1) // 범위 벗어난 경우
                    continue;
                if(lake[nx][ny] == 'L' && visit[nx][ny] == false){ // L인데 방문 X
                    success = true; // 탐색 성공
                    break; // 반복문 종료
                }
                if(lake[nx][ny] == '.' && visit[nx][ny] == false){ // 물인데 방문 X
                    Q.push({nx, ny}); // 큐에 위치 넣음
                    visit[nx][ny] = true; // 방문했다고 표시
                }
                if(lake[nx][ny] == 'X' && visit[nx][ny] == false){ // 얼음인데 방문 X
                    nextQ.push({nx, ny}); // 다음에 방문하기 위해 nextQ에 push
                    visit[nx][ny] = true; // 방문했다고 표시
                }
            }
        }
        if(success){ // 탐색 성공시
            cout << day << "\n"; // 걸린 날짜 출력
            break; // while문 종료
        }

        Q = nextQ; // 큐에 방문해야 할 nextQ를 넣음
        int watersize = waterQ.size(); // waterQ의 원소 개수

        while(watersize){ // 하루가 지나 얼음이 녹은 상황으로 바꿔줌
            auto temp = waterQ.front(); // waterQ의 맨 앞 원소 담음
            waterQ.pop(); // 담은 원소 제거

            for(int i = 0; i < 4; i++){ // 상하좌우 탐색 시작
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];
                if(nx < 0 || nx > r - 1 || ny < 0 || ny > c - 1) // 범위 벗어난 경우
                    continue;
                if(lake[nx][ny] == 'X'){ // 얼어있는 경우
                    waterQ.push({nx, ny}); // 위치 저장하고(push)
                    lake[nx][ny] = '.'; // 물로 바꿈
                }
            }
            watersize--;
        }
        day++; // 하루 증가
    }
}

여기서 auto란? → 타입 추론

- auto 키워드는 선언된 변수의 초기화 식을 사용해 해당 형식을 추론하도록 컴파일러에 지시

- 즉 초깃값의 형식에 맞춰 선언하는 인스턴스(변수)의 형식이 '자동'으로 결정 → 타입 추론(type inference)

실행결과