백준 1261번 알고스팟 문제 풀이

문제 설명

• 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다.
• 뚫린 방은 0, 벽은 1로 되어있다.
• (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하나?

문제를 보고 든 생각

• 최단 경로로 가야하나? (결론은 아니다)
• 가야 할 곳을 큐에 넣어서 전부 탐색해봐야겠다.
• DP 테이블을 활용할 수 있겠다.

간단한 풀이 설명

1. 입력받은 지도의 정보가 담긴 2차원 배열 G
2. w[i][j] = i, j 방에 왔을 때 부순 벽의 최소 개수 (DP 테이블)
3. 다음 가야할 방의 부셔야 할 벽의 수 + 현재까지 부신 벽의 수 < 다음 가야할 방의 부신 벽의 수
   ( G[nX][nY] + currCnt < w[nX][nY] ) 면 새로 갱신하고 큐에 넣어준다.
4. 이걸 다 하면 w[N][M]의 값은 N, M까지 가는데 부신 벽의 최소 수가 될 것이다.

코드

#include <iostream>
#include <queue>
#include <string>

#define MAX_N 101
#define MAX_W 987654321

using namespace std;

struct strt{
  int x, y;
};

int N, M;
int G[MAX_N][MAX_N];
int w[MAX_N][MAX_N];
int way4[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
queue<strt> q;

void getInput(){
  cin >> M >> N;

  for(int i=0; i<N; ++i){
    string str; cin >> str;
    for(int j=0; j<M; ++j){
      G[i][j] = str[j] - '0';
    }
  }
}

void initW(){
  for(int i=0; i<N; ++i){
    for(int j=0; j<M; ++j){
      w[i][j] = MAX_W;
    }
  }
}

void printW(){
  cout << "\n=============================\n";
  for(int i=0; i<N; ++i){
    for(int j=0; j<M; ++j){
      cout << w[i][j] << " ";
    }cout << "\n";
  }
}

int solve(){
  initW();
  q.push({0,0});
  w[0][0] = 0;

  while(!q.empty()){
    strt curr = q.front(); q.pop();
    for(int i=0; i<4; ++i){
      int nX = curr.x + way4[i][0], nY = curr.y + way4[i][1];
      if(nX < 0 || nY < 0 || nX >= N || nY >= M) continue;
      
      int currCnt = w[curr.x][curr.y];
      int nextCnt = G[nX][nY] + currCnt;
      int currNextCnt = w[nX][nY];
      if(nextCnt < currNextCnt){
        w[nX][nY] = nextCnt;
        q.push({nX, nY});
      }
    }
  }
  // printW();
  return w[N-1][M-1];
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  getInput();
  cout << solve();
  return 0;
}

보충

c0510gy의 조언에 의하면 우선순위 큐를 사용했을 때 더 빠른 결과를 가져올 수 있다고 한다. 똑똑한 녀석

• 부순 벽 값이 더 작은 애들 우선으로 둬서 n,m에 도달하면 바로 리턴