[백준 - 3197] 백조의 호수 - C++

분류: BFS /

 

문제

문제 링크

문제 설명

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 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..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

풀이

#include <iostream>
#include <queue>
using namespace std;

struct xy {int x, y;};
int R, C;
char board[1500][1501];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
char mark[] = {'1', '2'};
queue<xy> Q[2];
queue<xy> B;

bool OOB(int x, int y) { return x<0 || x>=R || y<0 || y>=C; }
bool isBeach(int x, int y) {
    for(int dir=4; dir--;) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if(OOB(nx, ny)) continue;
        if(board[nx][ny] == 'X') return true;
    }
    return false;
}
void melt() {
    for(int size = B.size(); size--;) {
        auto [x, y] = B.front(); B.pop();
        for(int dir=4; dir--;) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if(OOB(nx, ny)) continue;
            if(board[nx][ny] == 'X') {
                board[nx][ny] = '.';
                B.push({nx, ny});
            }
        }
    }
}
bool bfs(int k) {
    queue<xy> tmpQ;
    while(!Q[k].empty()) {
        auto [x, y] = Q[k].front(); Q[k].pop();
        bool wait = false;
        for(int dir=4; dir--;) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if(OOB(nx, ny)) continue;
            if(board[nx][ny] == mark[k]) continue;
            if(board[nx][ny] == mark[!k]) return true;
            if(board[nx][ny] == 'X') wait = true;
            else {
                board[nx][ny] = mark[k];
                Q[k].push({nx, ny});
            }
        }
        if(wait) tmpQ.push({x, y});
    }
    Q[k] = tmpQ;
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> R >> C;
    for(int i=0; i<R; i++) cin >> board[i];
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if(board[i][j] != 'X' && isBeach(i, j))
                B.push({i, j});
            if(board[i][j] == 'L') {
                board[i][j] = mark[Q[1].empty()];
                Q[Q[1].empty()].push({i, j});
            }
        }
    }

    int day = 0;
    while(!Q[0].empty()) {
        if(bfs(0)) break;
        if(bfs(1)) break;
        melt();
        day++;
    }
    cout << day;
}

입력을 받으며 백조를 발견하면 큐에 저장(`Q[1]`에 저장 후 `Q[0]`에 저장)

얼음 주변을 `B`에 저장

아이디어는 백조0이 갈 수 있는 곳을 모두 1로 마킹, 백조 1이 갈 수 있는 곳을 모두 2로 마킹

만나지 않았다면 얼음 녹이고 다시 수행

1. BFS로 L1가 갈 수 있는 곳을 모두 '1'로 마킹(`bfs(0)`)
   1. '2'로 마킹되어 있는 곳을 찾았다면 L1과 L2가 만날 수 있으므로 종료
   2. 빙판을 만나면 멈췄다가 내일 멈췄던 곳에서 다시 BFS를 돌며 확인(`tmp` 큐)
   3. 모든 확인이 끝나면 `tmp`큐에 멈춘 곳들을 내일을 위해 `Q`로 옮김
2. BFS로 L2가 갈 수 있는 곳을 모두 '2'로 마킹(`bfs(1)`)
   1. 1의 과정과 같듬
3. 빙판을 녹이고 하루 경과(`melt()`)
   1. 빙판 주변칸이 저장된 `B` 큐로 한 턴만 실행(BFS를 순차 실행)
   2. 빙판을 녹이고 빙판이 녹은 곳은 빙판 주변일 가능성이 있으므로 `B`에 push

 

문제에서 중요한 개념을 정리해보면 다음과같다.

• `해변`으로 BFS순차 실행을 통해 얼음 녹이기
• 두 백조를 다른 값으로 방문을 표시해 만날 수 있는지 확인하기
• 빙판을 만나면 내일 그 빙판이 녹으면 현재 자리에서 부터 BFS 시작하기위해 현재 위치를 따로 저장해놓기

얼음 주변 `해변` 을 큐에 저장해 얼음을 녹이는 것은 [백준 - 2573] 빙산 문제에서 생각한 개념이다.

방문값을 다르게 하는 개념과 BFS를 한 단계씩 실행하는 개념 역시 앞서 많은 문제를 풀어오며 나름대로 정리했다.

BFS를 진행하다 현재자리에 멈췄다가 멈춘 자리에서 나중에 다시 실행하는 건 이 문제가 처음이 아닌가 한다.

 

# 오답

틀렸는데 3일정도 고민해도 틀린 부분을 못찾아서 질문을 올렸었다.

오답 코드와 위 코드는 딱 한글자가 다른데 `board[1500][1501]`다. 열의 크기를 1501로 설정해줘야한다.

[백준 - 4179] 불! 문제에서도 정리했었는데 생각 못하고 3일동안 고민했다.

내가 올린 질문에 답변에도 정리를 해놨지만 다시 정리하면 다음과같다.

 

board[][]는 메모리에서 연속된 공간에 있기 때문에 `C`가 최댓값 1500인 경우 `board[i+1]`의 마지막 널문자가 `board[i]`의 첫글자를 덮어 쓸 수 있다.

따라서 아래 방법중 하나로 널문자를 고려하여 입력을 받아야한다.

// 1. 한글자씩 저장
char board[1500][1500];
cin >> board[i][j];

/ /2. 널문자 저장공간 확보
char board[1500][1501];
cin >> board[i];

// 3. 스트링 사용
string board[1500];
cin >> board[i];

 

ps. 다음 코드를 실행하고 입력이 저장된 결과를 확인해 실험해보자.

#include <iostream>
using namespace std;

int main() {
    char aaa[3], bbbb[4];
    cin >> aaa >> bbbb;
    
    cout << '\n';
    for(int i=0; i<3; i++) 
        cout << '(' << aaa[i] << ')';
    cout << '\n';
    for(int i=0; i<4; i++) 
        cout << bbbb[i];
}

/*
입력:
abc
1234

예상 출력:
(a)(b)(c)
1234

실제 출력:
()(b)(c)
1234
*/

이는 메모리상에 `bbbb`배열 `aaa`배열이 연속적으로 붙어있어 생기는 문제다.

뒤에 입력된 "1234"의 널문자가 `bbbb`배열의 크기를 초과해 `aaa[0]`에 저장되어 생기는 문제이다.

`bbbb`의 크기를 5로 변경해 "1234"의 널문자가 `bbbb`에 저장되도록 하면 문제가 해결된다.