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

문제

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

3197번: 백조의 호수

 

 

풀이 과정

해당 문제를 정말 많이 고민하면서 풀었지만 계속 메모리 초과가 발생했다. 메모리 초과에 의해서 문제를 풀지 못했던 적은 처음이라 이런저런 경우를 많이 테스트해보며 과정을 적으려 한다.

 

1) int -> char 변경 (실패)

처음엔 전체 호수의 상태를 저장하기 위해 int map [1501][1501]를 이용했었는데, 여기서 메모리가 초과되었나 하고 고쳐보았다. 

(하지만 해당 배열은 약 9MB 정도로 계산되는데 문제의 메모리 제한은 256MB였다.)

 

2) 함수 내부에 선언되었던 queue를 전역 변수 위치로 빼내기 (실패)

보통 메모리 초과의 문제는 DFS, BFS와 같이 함수 호출이 중복되어 메모리를 초과하였거나, queue 영역에 중복된 노드의 추가로 인해 그러한 오류가 발생한다고 했다. 따라서 함수 내부적으로 선언된 queue를 모두 전역 변수 위치로 이동시켰으며, BFS를 통해 탐색하는 노드들을 확인했는데 딱히 중복이 발견되지는 않았다.

 

3) 다른 사람들의 풀이와 비교

[풀이 링크 1]

문제를 열심히 고민하다 메모리 초과를 해결하기 위해 다른 사람들의 코드를 참고하며 어떤 부분이 문제가 되는지 확인하는 도중 필자가 생각한 방식과 매우 비슷한 형태의 풀이를 발견했다. 현재까지 코드를 유심히 살펴보았는데, 메모리 초과가 발생할 차이를 아직 발견하지 못했다. 따라서 필자의 코드와 해당 링크의 코드를 비교한 뒤, 문제를 찾으면 해당 내용을 추가할 예정이다.

 

 

소스 코드

/* 
 * baekjoon 3197
 * 
 * 백조의 호수
 * 
 * https://www.acmicpc.net/problem/3197
 * 
 * 
 * 입력 받는 char
 * . -> 물
 * X -> 얼음
 * L -> 백조
 * 
 * 백조가 있는 위치는 물이다. 
 * 
 * 1) 얼음 기록
 * 얼음을 queue 에 기록한다.
 * queue에 적힌 얼음들을 탐색하며 테두리가 물과 맞닿지 않은 얼음을 next_ice_q 에 기록한다.
 * 물과 맞닿지 않은 얼음은 다음 날짜에 남아있을 얼음을 의미한다.
 * 
 * 지도를 업데이트 하며,
 * ice_q = next_ice_q 를 수행해서 다음 날짜의 얼음을 표시한다.
 * 
 * 2) 백조가 갈 수 있는 길 기록
 * 백조가 갈수 있는 길은 지도에 L 로 표시한다.
 * 초기 입력시 두개의 L을 입력받는다. 
 * 둘 중 하나 (먼저 입력받은)의 좌표의 값은 L로 표시하고, 다른 좌표의 값은 얼음으로 표시한다. (이때 좌표는 기록)
 * 
 * 백조가 BFS형태로 L인 부분과 X인 부분 (이미 방문 했던 부분과 얼음인 부분)은 방문하지 않도록
 * 설정하여 탐색한다.
 * 
 * 탐색 후 위에서 기록했던 도착지의 좌표가 L로 바뀌었다면 두 백조가 만날 수 있는 길이 만들어진 것이므로
 * 반복을 종료하며 날짜를 출력한다.
 * 
 * 
 */

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int r,c;
const int max_rc = 1501;
char map[max_rc][max_rc];

pair<int,int> swans[2];
queue<pair<int,int>> ice_q, s, next_ice_q, next_s;
void print_map(){
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cout << map[i][j];
        }
        cout << "\n";
    }   
    cout << "\n";
}


void Input(){
    cin >> r >> c;
    char temp;
    int swan_cnt = 0;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> temp;
            if(temp == 'L'){
                swans[swan_cnt].first = i;
                swans[swan_cnt].second = j;
                swan_cnt ++;
                map[i][j]='.';
            }
            else if(temp == '.') map[i][j]=temp;
            else if(temp == 'X'){
                map[i][j]=temp;
                ice_q.push({i,j});
            }
        }
    }
    s.push({swans[0].first, swans[0].second});
    
}

int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
bool check_melting(int x, int y){
    bool flag = false;
    for(int i=0;i<4;i++){
        int nx = x+dir[i][0];
        int ny = y+dir[i][1];
        if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        // 4방향 중 하나라도 물이라면 flag 는 true가 된다.
        if(map[nx][ny] != 'X') flag = true;
    }

    return flag;
}


void melting_ice(){
    while(!ice_q.empty()){
        int x = ice_q.front().first;
        int y = ice_q.front().second;
        // cout << x << " " << y << "\n";
        ice_q.pop();
        //녹지 않은 얼음들은 next_ice_q 에 저장
        if(!check_melting(x,y)){
            next_ice_q.push({x,y});
        }
    }
    memset(map,'.',sizeof(map));
    while(!next_ice_q.empty()){
        int x = next_ice_q.front().first;
        int y = next_ice_q.front().second;
        next_ice_q.pop();
        map[x][y] = 'X';
        ice_q.push({x,y});
    }
    
}


/*
 * 한번 다녀간 길은 L로 표시한다. 곧 녹을 얼음은 next_ice_q 를 통해 관리하므로,
 * 추가 탐색할 칸은 next_s로 관리한다.
 */

bool is_way(){
    while(!s.empty()){
        int x = s.front().first;
        int y = s.front().second;
        map[x][y]='L';
        s.pop();
        for(int i=0;i<4;i++){
            int nx = x+dir[i][0];
            int ny = y+dir[i][1];
            if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if(map[nx][ny]=='X'){
                next_s.push({nx,ny});
                continue;
            }
            if(map[nx][ny] == 'L') continue;
            
            s.push({nx,ny});
        }
    }
    
    s = next_s;
    int end_x = swans[1].first;
    int end_y = swans[1].second;
    if(map[end_x][end_y]=='L') return true;
    else return false;
}


void solve(){
    int day = 0;
    while(!is_way()){
        melting_ice();
        day++;
    }
    cout << day;
}

int main(){
    ios_base::sync_with_stdio(0);   
    cin.tie(0);
    Input();
    solve();
    return 0;
}

 

결과 및 후기

참패했다. 메모리 초과로 인해 문제를 틀렸던 것은 최근에 경험하지 못했던 터라 이런저런 검색이 더 필요하다고 느꼈다. 주로 언급되는 내용들을 처리했는데도 잘 해결이 되지 않았다. 필자가 구상한 풀이 방법과 매우 유사했던 링크의 풀이를 우선 답으로 제출하고 다른 정답자들의 코드를 더 많이 공부해본 뒤 문제가 뭐였는지 파악해봐야 할 것 같다.