[C++] 백준 1261 - 알고스팟 (메모리 초과 이슈)

• 문제

• 풀이 방법

• 초기 코드

• 초기 코드의 문제

• 해결 방법

• 최종 코드

백준 1261 - 알고스팟
난이도 : 골드 4
시간 : 30분 소요

문제

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

1261번: 알고스팟

 

풀이 방법

 

해당 문제는 bfs를 사용하면 쉽게 풀릴 줄 알았다. 그래서 깊게 고민해보지 않고, 바로 코드를 적었지만 메모리 초과가 발생했다.

 

초기 코드

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


using namespace::std;

int N, M;
int map[101][101];
int v[101][101];

int result = 999999999;

int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

void bfs(int y, int x){
    
    queue<pair<pair<int, int>, pair<int, int>>> q;
    
    v[y][x] = 1;
    q.push({{y, x}, {0,0}});
    
    while(!q.empty()){
        int ny = q.front().first.first;
        int nx = q.front().first.second;
        int cnt = q.front().second.first;
        q.pop();
        
        if(ny == N && nx == M){
            result > cnt ? result = cnt : 1;
            continue;
        }
        
        v[ny][nx] = 1;
        
        for(int i=0; i<4; i++){
            int ty = ny + ud[i];
            int tx = nx + lr[i];
            
            if(v[ty][tx] == 0){
                if(ty >= 1 && tx >= 1 && ty <= N && tx <= M){
                    
                    if(map[ty][tx] == 1){
                        q.push({{ty, tx}, {cnt+1, 0}});
                    }else{
                        q.push({{ty, tx}, {cnt, 0}});
                    }
                }
            }
        }
    }
    
}

int main(){
    scanf("%d %d", &M, &N);
    
    for(int i=1; i<=N; i++){
        string tmp;
        cin >> tmp;
        for(int j=1; j<=M; j++){
            map[i][j] = tmp[j-1] - 48;
        }
    }
    
    bfs(1,1);
    
    printf("%d\n", result);
}

 

 

초기 코드의 문제

1. 벽을 최소로 부신 루트가 특정 정점을 나중에 방문할 수 있다. 하지만 벽을 많이 부신 루트가 이미 방문처리를 해버려서 해당 정점을 방문하지 못하는 경우가 발생한다.

 

2. 큐에 너무 많은 데이터가 들어가게 되어 메모리 초과가 발생한다.

 

 

해결 방법

1. 방문을 한 정점을 다시 방문할 수 있도록 벽을 부순 횟수를 2차원 배열로 저장한다. 

    wall[i][j] : (i,j) 위치에 도달하기 까지 벽을 부순 최소 횟수

 

따라서, 재방문하는 정점이면 이전에 저장되어 있는 wall 값과 현재 루트로 갔을 때 벽을 부순 횟수를 비교하여 더 작은 값으로 갱신한다.

이전 값이 아닌 새로운 값을 갱신하게 되면 해당 정점을 큐에 넣는다.

 

2. 1번 방법을 취하게 되면 모든 정점을 큐에 넣는 것이 아닌 조건에 따라 넣기 때문에 메모리 초과 이슈도 해결할 수 있다.

 

 

최종 코드

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

#define MAX 101

using namespace::std;

int N, M;
int map[MAX][MAX];
int wall[MAX][MAX];


int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

void bfs(int y, int x){
    
    queue<pair<int, int>> q;
    
    q.push({y, x});
    
    while(!q.empty()){
        int ny = q.front().first;
        int nx = q.front().second;
        int cnt = wall[ny][nx];
        q.pop();
        
        if(ny == N && nx == M){
            continue;
        }
        
        
        for(int i=0; i<4; i++){
            int ty = ny + ud[i];
            int tx = nx + lr[i];

            if(ty >= 1 && tx >= 1 && ty <= N && tx <= M){
                if(map[ty][tx] == 1){
                    if(wall[ty][tx] > cnt+1){
                        wall[ty][tx] = cnt+1;
                        q.push({ty, tx});
                    }
                }else{
                    if(wall[ty][tx] > cnt){
                        wall[ty][tx] = cnt;
                        q.push({ty, tx});
                    }
                }
            }
            
        }
    }
    
}

int main(){
    scanf("%d %d", &M, &N);
    
    for(int i = 1; i<=N; i++){
            for(int j = 1; j<=M; j++){
                wall[i][j] = INT_MAX;
            }
        }
    
    for(int i=1; i<=N; i++){
        string tmp;
        cin >> tmp;
        for(int j=1; j<=M; j++){
            map[i][j] = tmp[j-1] - 48;
        }
    }
    wall[1][1] = 0;
    bfs(1,1);
    
    printf("%d\n", wall[N][M]);
}