백준 1261번 알고스팟 (C++)

문제 링크 : www.acmicpc.net/problem/1261

1261번: 알고스팟

로직을 먼저 정하지 않고 대충보면서 풀다가 놓친 부분이 몇몇 있었던 문제이다.

 

먼저 이 문제에서 유의사항은 다음과 같다.

1. 숫자가 아닌 문자열로 주어진다.

2. 세로, 가로가 아닌 가로, 세로로 n과 m이 주어진다.

 

문제 풀이는 다음과 같다. 

1. 가로, 세로로 값이 주어진다. 때문에 편의를 위해 n,m이 아닌 m,n의 순서로 값을 입력 받는다.

2. 숫자가 아닌 문자로 값이 주어진다. 때문에 값을 입력받을때마다 -'0'을 해주어 문자형을 숫자형으로 저장해준다.

3. 큐를 2개 만든다. 하나는 빈방을 통해 거쳐온 길을 저장할 큐이고, 다른 하나는 벽을 뚫고 갔을때 저장할 큐이다.

4. 시작지점 [1][1]을 큐에 삽입하고, 해당 지점은 bool문으로 방문여부를 true로 저장한다.

5. 현재 지점에서 4방위를 기준으로, 해당 지점을 방문한 적이 없으면 해당 값을 큐에 저장한다.

이때 큐에 저장하는 로직이 중요한데, 아래 코드를 봐보자.

        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny>=1&&ny<=n&&nx>=1&&nx<=m&&!ch[ny][nx]){
                ch[ny][nx] = true; // 중요
                if(arr[ny][nx]==1){ // 벽
                    q2.push({ny,nx});
                    dp[ny][nx] = dp[y][x]+1;
                }
                else{ // 길
                    q1.push({ny,nx});
                    dp[ny][nx] = dp[y][x];
                }
            }
        }

먼저 해당 지점을 방문한 적이 없고, 해당 지점이 범위를 초과하지 않으면 곧바로 해당 지점의 방문 여부를 true로 바꿔주자.

true로 먼저 바꿔주지 않을 경우, 온갓 값들이 큐에 저장되어 결국 메모리 초과가 날 수 밖에 없다.

만약 해당 지점이 벽이라면 큐2에 저장해주고, 벽을 부순 횟수는 움직이기 이전 횟수의 +1를 저장해준다.

빈방이라면 큐1에 저장해주자. 벽을 부순 횟수는 움직이기 이전 횟수와 동일하다.

 

6. 아래 코드는 위 코드의 바로 뒤에 오는 코드이다.

        if(q1.empty()){
            q1 = q2;
            q2 = queue<pair<int,int>>();
        }

만약 q1이 비어있으면 = 벽을 부수지 않고 갈 수 있는 길들이 고갈되었다면, 이제는 벽을 부순 상태에서 새로운 길을 개척하는 방법밖에 없다는 뜻이다. 때문에 q1(벽을 부수지 않고 빈 방을 통해 갔던 루트)에 q2값들을 그대로 복사해주고, q2는 초기화 해준다.

이렇게 해서 while(!q1.empty())의 코드는 모든 지점을 방문하기 전까지, 혹은 답이 출력되기 전까지 계속해서 운영될 수 밖에 없다.

 

#include <iostream>
#include <queue>
#define MAX 101
using namespace std;

bool ch[MAX][MAX];
int arr[MAX][MAX] = {0,},dp[MAX][MAX] = {0,},n,m,my[]={1,-1,0,0,},mx[]={0,0,1,-1},y,x,ny,nx;
char c;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> m >> n; // m = 4, n = 2
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> c;
            arr[i][j] = c-'0';
        }
    }
    queue<pair<int,int>> q1;
    queue<pair<int,int>> q2;
    q1.push({1,1});
    ch[1][1] = true;
    while(!q1.empty()){
        y = q1.front().first;
        x = q1.front().second;
        q1.pop();
        if(y==n&&x==m){
            cout << dp[y][x] << "\n";
            exit(0);
        }
        for(int i=0; i<4; i++){
            ny = y+my[i];
            nx = x+mx[i];
            if(ny>=1&&ny<=n&&nx>=1&&nx<=m&&!ch[ny][nx]){
                ch[ny][nx] = true; // 중요
                if(arr[ny][nx]==1){ // 벽
                    q2.push({ny,nx});
                    dp[ny][nx] = dp[y][x]+1;
                }
                else{ // 길
                    q1.push({ny,nx});
                    dp[ny][nx] = dp[y][x];
                }
            }
        }
        if(q1.empty()){
            q1 = q2;
            q2 = queue<pair<int,int>>();
        }
    }
    return 0;
}