BOJ : 3197 백조의 호수 (테스트 케이스 첨부)

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

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #2 - Seniors 2번

2573 빙산, 3055 탈출 문제의 하드버전

문제 해결 순서

1. 백조의 만남 가능 여부

2. 해빙. 테두리만 녹이기

3. 만날 때까지 반복

해결 방법은 3055 탈출문제와 유사하지만 R, C 값이 1500이기 때문에 백조 만남 가능 여부 탐색시 TLE가 발생할 수도 있다. (이거 때문에 개고생)

문제 해결 방안

제일 처음 백조 이동 후 만날 수 없다면 방문 한 곳은 다시 방문할 필요없다.

만날 수 있냐 없냐만 확인하면 가능하기 때문에 백조의 위치를 변경해주면 된다.

그렇다면? 얼음이 녹는 부분에서 탐색하면 시간을 줄일 수 있다. 어처피 녹는 곳이 만날 수 있는 길이 될테니 (line : 33의 이유가 된다.)

테스트 케이스

test_data.zip

.i01 : 1번 입력 케이스 / .o01 : 1번 출력 결과

freopen("labudovi.i05", "r", stdin); 

파일 입출력으로 입력받으세요. 

#include <cstdio>
#include <queue>
using namespace std;
int R,C, cnt=0;
char map[1502][1502];
bool visited[1502][1502], thaw_visited[1502][1502];// 전자 : 백조꺼, 후자 : 얼음꺼
queue<pair<int, int>> q, thaw; // q : 백조 위치, thaw : 얼음의 테두리
pair<int, int> S,E;
int pr[4]={1,-1,0,0};
int pc[4]={0,0,1,-1};
bool flag = 0; //0 : 맨 처음 테두리 찾기, 1 : 이후에 녹는 테두리는 물(.)이 됨
 
void MeltIce(int r, int c){
    thaw_visited[r][c]=1;
    if(map[r][c]=='X'){
        thaw.push({r, c});
        if(flag) map[r][c]='.';
    }
    else {
        for(int i=0;i<4;i++){
            int nr = r+pr[i], nc = c+pc[i];
            if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if(thaw_visited[nr][nc]) continue;
            MeltIce(nr, nc);
        }
    }
    return;
}
 
//만남가능여부
bool canMeetFuckingSwan(){
    queue<pair<int, int>> swan_temp;
    swap(swan_temp, q); //swan_temp에는 다음 좌표가 push되고 q에는 얼음의 테두리가 push된다.(이유는 위에 설명)
    while(!swan_temp.empty()){
        int r = swan_temp.front().first, c = swan_temp.front().second;
        swan_temp.pop();
        if(r==E.first && c==E.second){
            return true;
        }
        for(int i=0;i<4;i++){
            int nr = r+pr[i], nc = c+pc[i];
            if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if(visited[nr][nc]) continue;
            if(map[nr][nc]=='X') q.push({nr, nc});
            else swan_temp.push({nr ,nc});
            visited[nr][nc]=1;
        }
    }
    return false;
}
 
int main(){
    scanf("%d%d",&R,&C);
    bool first=0;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            char c;
            scanf(" %c",&c);
            map[i][j]=c;
            if(c=='L'){
                if(!first){
                    first= 1;
                    S.first=i, S.second=j;
                }
                else E.first=i, E.second=j;
            }
        }
    }
    
    // 테두리 얼음 찾기
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
            if(!thaw_visited[i][j] && map[i][j]!='X')
                MeltIce(i,j);
    flag = 1;
    q.push(make_pair(S.first, S.second));
    visited[S.first][S.second]=1;
    
    while(!canMeetFuckingSwan()){
        cnt++;
        
        //해동
        queue<pair<int, int>> temp;
        swap(temp, thaw);
        while(!temp.empty()){
            int r=temp.front().first, c=temp.front().second;
            temp.pop();
            MeltIce(r, c);
        }
        
    }
    
    printf("%d\n",cnt);
    
    
    return 0;
}