[BOJ][C++] 백준 3197번: 백조의 호수 (Platinum V)

https://www.acmicpc.net/problem/3197

 

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

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

출력

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

 

풀이

"백조 BFS -> 물 BFS"

이 과정을 반복하면 되는 문제

 

매일 BFS를 두번씩 해야한다.

이때 bfs 시작점을 매번 이중 반복문으로 구하려하면 바로 2%에서 시간초과가 뜬다.

bfs를 할 때 내일의 시작점이 될 후보들을 미리 큐에 넣어두고, 그 다음날 이 큐를 사용해야한다

 

1. 물 BFS : melt()

// bfs : 빙판(X) -> 물(.)
void melt() {
    queue<ci>q = water; // 큐에 저장된 물의 좌표들에서 bfs 시작
    while(!water.empty()) { // 다음 물 좌표들은 초기화
        water.pop();
    }

    while(!q.empty()) {
        ci cur = q.front();
        q.pop();
        
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            if(x<0 || x>=r || y<0 || y>=c) continue;
            
            // 빙판이라면 물로 바꾸고 해당 위치 저장 (내일 물이 됨)
            if(v[x][y] == 'X') {
                v[x][y] = '.';
                water.push({x,y});
            }
            // 빙판이 아니라면(물이나 백조라면) 패스
        }
    }
    return;
}

 

2. 백조 BFS : swim()

 

// bfs : 물(.) or 빙판(X) -> 백조(L)
bool swim() {
    vector<vector<bool>>visited(r, vector<bool>(c, false)); // 방문여부 표시

    queue<ci>q = swan; // 큐에 저장된 백조 위치에서 bfs 시작
    while(!swan.empty()) { // 다음 큐 초기화
        swan.pop();
    }

    while(!q.empty()) {
        ci cur = q.front();
        q.pop();
        
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            if(x<0 || x>=r || y<0 || y>=c) continue;
            if(visited[x][y]) continue;
            
            visited[x][y] = true;
            
            if(goal.first==x && goal.second==y) {
            // 다음 좌표가 다른 백조의 위치와 같음 = 백조 두마리가 만남
                return true;
            } else if(v[x][y] == '.') { 
            // 다음 좌표가 물 = 백조가 차지함
                v[x][y] = 'L';
                q.push({x,y});
            } else if(v[x][y] == 'X') { 
            // 다음 좌표가 빙판 = 더 못나아감 = 내일 현재 위치부터 시작하도록 좌표 저장
                swan.push({cur.first, cur.second});
            }
        }
    }
    return false;
}

 

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ci;

int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
	    
int r,c;
vector<string> v;

ci start={-1,-1}, goal;
queue<ci> water, swan;

// bfs : 물(.) or 빙판(X) -> 백조(L)
bool swim() {
    vector<vector<bool>>visited(r, vector<bool>(c, false));

    queue<ci>q = swan;
    while(!swan.empty()) {
        swan.pop();
    }

    while(!q.empty()) {
        ci cur = q.front();
        q.pop();
        
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            if(x<0 || x>=r || y<0 || y>=c) continue;
            if(visited[x][y]) continue;
            
            visited[x][y] = true;
            
            if(goal.first==x && goal.second==y) { // 백조 두마리가 만남
                return true;
            } else if(v[x][y] == '.') { // 물로 이동
                v[x][y] = 'L';
                q.push({x,y});
            } else if(v[x][y] == 'X') { // 물이 될 운명
                swan.push({cur.first, cur.second});
            }
        }
    }
    return false;
}

// bfs : 빙판(X) -> 물(.)
void melt() {
    queue<ci>q = water;
    while(!water.empty()) {
        water.pop();
    }

    while(!q.empty()) {
        ci cur = q.front();
        q.pop();
        
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            if(x<0 || x>=r || y<0 || y>=c) continue;
            if(v[x][y] == 'X') {
                v[x][y] = '.';
                water.push({x,y});
            }
        }
    }
    return;
}


int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	// 입력
	cin >> r >> c;
	v.assign(r, "");
	for(int i=0; i<r; i++) {
	    cin >> v[i];

	    for(int j=0; j<c; j++) {
	        if(v[i][j] != 'X') {
	            water.push({i,j});
	        }
	        if(v[i][j] == 'L') {
	            if(start.first==-1 && start.second==-1) {
	                start = {i,j};
	                swan.push({i,j});
	            } else {
	                goal = {i,j};
	            }
	        }
	    }
	}

	// 풀이
	int time = 0;
	while(true) {
	    if(swim()) {
	        break;
	    }
	    melt();
	    time++;
	}
	
	// 출력
	cout << time;
	
    return 0;
}

 

melt 함수를 먼저 이해하고 swim 함수를 이해하는게 나을것이다