(C++) - 백준(BOJ) 2665번 : 미로만들기

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

2665번: 미로만들기

bfs로 해결한 문제였습니다.

 

풀이방법

 1. 최소로 벽을 부수는게 0일 수 있으므로 정답을 확인할 배열 ck를 -1로 초기화해줍니다.

 

 2. 입력을 받은 후 bfs를 시행합니다.

 

   2-1. 시작점 0,0을 queue에 push한 후 ck를 0으로 갱신해줍니다. 

 

   2-2. q가 빌 때까지 수행하는데 주의할 것은 최단거리로 이동했을 때 바꿔준 방의 개수가 최소임을 보장할 수 없는 점입니다. 갱신해줘야하는 시점을 잘 정해야합니다. 4방향으로 다음 장소로 이동할 때 검은 방이라면 흰 방으로 바꿔줘야합니다. 하지만 다른 곳에서 도착했을 때 바꾼 개수가 더 작을 수 있으므로 if문을 걸어줘야 합니다. 만약 도착했을 때 바꾼 방의 개수 + 1이 기존 값보다 작거나 아직 방문안한 곳(ck[nx][ny] == -1)이면 갱신해줍니다. 반대의 경우 도착했을 때 바꾼 방의 개수가 기존 값보다 작거나 아직 방문안한 곳(ck[nx][ny] == -1)이면 갱신해줍니다.

 

  2-3. ck[n-1][n-1]을 반환해줍니다.

 

3. 반환값을 출력해줍니다.

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int n;
int ck[51][51], board[51][51]; //마지막 0은 부순상태, 안부순 상태
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};

int bfs(){
    queue <pii> q;
    q.push({0,0});
    ck[0][0] = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= n) continue;
            if(!board[nx][ny]){
                if(ck[nx][ny] == -1 || ck[nx][ny] > ck[x][y] + 1){
                    ck[nx][ny] = ck[x][y] + 1;
                    q.push({nx,ny});
                }
            }
            else{
                if(ck[nx][ny] == -1 || ck[nx][ny] > ck[x][y]){
                    ck[nx][ny] = ck[x][y];
                    q.push({nx,ny});
                }
            }
        }
    }
    return ck[n-1][n-1];
}

int main(){
    memset(ck,-1,sizeof(ck));
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%1d",&board[i][j]);
        }
    }
    cout << bfs() << '\n';
}