프로그래머스 거리두기체크하기 // 2차원벡터다루기 형식, 종이에그려보며 규칙세우기 , 2차원배열 초기화방법

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

* 2차원벡터다루기 형식

vector<vector<string> places

- main : for(auto place : places)

if(check) bfs(place)  //이후 place[y][x]로 접근하라.

 

- check

for(i=0-5, j=0-5)

if(place[y][x]==사람) bfs there

 

* 2차원배열 초기화방법

bool visit[5][5]={false};

 

* 종이에그려보며 규칙세우기.

POOOP

OXXOX

OPXPX

OOXOX

POXXP

for(모든P bfs)

--------------------------------

- bfs

거리가 2초과-> 스킵

거리가 2이하 and 거기가 사람임 -> false

for(4방탐색)

범위쳌

방문함 ->스킵

next==x -> 스킵

방문처리

큐푸쉬

 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

struct Point{
    int y;
    int x;
    int dist;
};
bool bfs(vector<string> place,int y, int x){
    queue<Point> q;
    q.push({y,x,0});
    bool v[5][5]={false};
    v[y][x]=1;
    
    while(q.size()){
        Point curr=q.front(); q.pop();
        if(curr.dist>2) continue;
        //거리 2이하 and 초기위치아님 and 사람을만낫다 -> false
        if(curr.dist!=0 and place[curr.y][curr.x]=='P') return false;
        
        for(int i=0;i<4;++i){
            int ny=curr.y+dy[i];
            int nx=curr.x+dx[i]; 
            
            if(ny<0 ||ny>=5 || nx<0||nx>=5) continue;
            if(v[ny][nx]) continue;
            if(place[ny][nx]=='X')continue;
            
            v[ny][nx]=1;
            q.push({ny,nx,curr.dist+1});
        }
    }
    return true;
    
}

//사람에 대해 bfs 돌려주기
bool check(vector<string> place){
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            if(place[i][j]=='P'){
                if(bfs(place,i,j)==false) return false;
            }
        }
    }
    //모든 사람에대해 실패가 아니면
    return true;
    
}
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(vector<string> place : places){
        if(check(place)) answer.push_back(1);
        else answer.push_back(0);
        
    }
    return answer;
}