[백준 알고리즘] 미로만들기 (2665).txt

//미로만들기 (2665)

//1. 어렵게 생각하지 않고, visit에 흰색으로 바꾼 상태를 저장함
//2. 한번도 안방문한 상태(-1)이면 현재값 저장,
//3. 만약 뒤에 temp.count값이 visit에 저장되어 있는 값보다 적을 경우에는 접근 가능하도록 만듦

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef struct cell{
    int r, c;
    int count;
}Cell;

int rdir[4] = {-1,0,1,0};
int cdir[4]= {0,1,0,-1};
int arr[51][51];
int visit[51][51];
int black;
bool check = false;
int result =99999999;
int main(){
    int n;
    scanf("%d", &n);
    for(int i =0;i<n; i++){
        string temp;
        cin >> temp;
        
        for(int j =0;j<temp.size(); j++){
            arr[i][j] = temp[j]-'0';
        }
    }
    
    for(int i =0;i<n; i++){
        for(int j =0;j<n; j++){
            visit[i][j] = -1;
        }
    }
    
    
    queue <Cell> root;
    root.push({0,0,0});
    
    while(!root.empty()){
        Cell temp = root.front();
        root.pop();
        
        if(temp.r == n-1 && temp.c == n-1){
            result = min(temp.count, result);
            check = true;
        }
        else{
            for(int i =0;i<4; i++){
                int nowR = temp.r + rdir[i];
                int nowC = temp.c + cdir[i];
                
                if(0<=nowR && nowR<n && 0<=nowC && nowC<n){
                    if(arr[nowR][nowC] == 0){
                        if(visit[nowR][nowC] == -1 ||visit[nowR][nowC] > temp.count+1){
                            visit[nowR][nowC] = temp.count +1;
                            root.push({nowR, nowC, temp.count+1});
                        }
                        
                    }
                    else{ //1 일때
                        if(visit[nowR][nowC] == -1 ||visit[nowR][nowC] > temp.count){
                            visit[nowR][nowC] = temp.count;
                            root.push({nowR, nowC, temp.count});
                        }
                    }
                }
            }
        }
    }
    printf("%d", result);
    
    return 0;
}