개발 블로그

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

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

접근 방법

visit[][]로 방문 여부를 체크해야하나 싶었는데, 그렇게 하면 나중에 방문한 경우가 더 적게 벽을 부신 경우가 될 수 있기 때문에 다른 방법을 고려해야 했다.

즉, 다음 방문할 칸이 벽이던 방이던, 갱신 조건(더 적게 벽을 부신 경우)을 만족할 경우에만 Queue에 push 해주면 된다. 그러면 마지막에 cntWall[N][M]에서 상하좌우로 탐색을 할 때 범위체크에서 우/하 방향이 걸러지고 상/좌의 경우에는 갱신조건을 만족하지 못하므로(cntWall가 같으므로) 더이상 Queue 에 Push 하지 않고 while문을 벗어나게 된다. 

(while문 안에 if 조건문으로 탈출 조건을 따로 안 써줘도 된다.)

주의할 점

처음에 메모리 초과가 난 이유가 Queue에 너무 많은 원소가 들어가서였다. 그 코드에서는 범위 체크만 통과하면 바로 Queue에 next 칸을 push 했었다. 

수정된 아래의 코드처럼 갱신 조건을 만족할 때만 Queue 에 push 해주면 메모리초과가 안 뜬다.

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

#define MAX 101

int N,M;
int map[MAX][MAX];
queue<pair<int,int>> que;

int cntWall[MAX][MAX];

//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

void BFS(){
    
    while(!que.empty()){

        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr<1 || nr>N || nc<1 || nc>M) continue;		//범위 체크
	
            if(map[nr][nc] == 1){		//다음 칸이 벽일 때
                
                if(cntWall[nr][nc] > cntWall[r][c]+1){		//갱신 조건
                    cntWall[nr][nc] =cntWall[r][c]+1;
                     que.push(make_pair(nr,nc));
                }
                
            }
            else{						//다음 칸이 방일 때
                if(cntWall[nr][nc]>cntWall[r][c]){			//갱신 조건
                    cntWall[nr][nc] = cntWall[r][c];
                    que.push(make_pair(nr,nc));
                }
            }
        }
    }
}

int main(){

    cin >> M >> N;
    string str;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            cntWall[i][j] = 1000;			//최대 값으로 초기 설정
        }
    }
    
    for(int i = 1; i<=N; i++){
        cin >> str;
        for(int j = 1; j<=str.length(); j++){
            map[i][j] = str[j-1]-'0';
        }
    }
    //입력받을 때 동일한 방법
    /* for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            scanf( "%1d", &map[i][j] );
        }
    }*/
   
    
    que.push(make_pair(1,1));
    cntWall[1][1] = 0;          //항상 뚫려 있다고 했으므로 0으로 초기 설정 가능
    
    BFS();
    
    cout << cntWall[N][M];
   
    
    return 0;
}