[BaekJoon] 2066 미로만들기 :: monton

문제

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

풀이

bfs를 이용하여 black이라는 배열에 현재 인덱스에서 검은방은 몇개나 바꿨는지 저장

1. bfs를 이용하여 상하좌우 탐색

2. 다음 인덱스 탐색하여 검은 방이 여태 몇개 있었는지 저장

  2-1. 다음 방이 흰방일 경우 - 현재 인덱스와 저장된 인덱스의 값중 작은 값 저장

  2-2. 다음 방이 검은방일 경우 -  현재 인덱스+1와 저장된 인덱스의 값중 작은 값 저장

3. 마지막 배열에 저장된 값 출력

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int N,flag,ans;
int arr[51][51];
int visit[51][51];
int black[51][51];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int main() {
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            black[i][j] = 10000000;
        }
    }
 
 
    queue <int> qx, qy, qb;
    qx.push(0), qy.push(0);
    visit[0][0] = 1;
    black[0][0] = 0;
 
    while (!qx.empty()) {
        int cnt = qx.size();
        while (cnt--) {
            int x = qx.front();
            int y = qy.front();
            qx.pop(), qy.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                //if (visit[nx][ny]) continue;
                if (arr[nx][ny]&& black[nx][ny] > black[x][y]) {
                    black[nx][ny] = black[nx][ny] < black[x][y] ? black[nx][ny] : black[x][y];
                    qx.push(nx), qy.push(ny);
                }
                else if(!arr[nx][ny] && black[nx][ny] > black[x][y]+1){
                    black[nx][ny] = black[nx][ny] < black[x][y]+1 ? black[nx][ny] : black[x][y]+1;
                    qx.push(nx), qy.push(ny);
                }
            }
        }
    }
    printf("%d", black[N - 1][N - 1]);
}