[세모] 프로그래머스 거리두기확인하기 c++ // bfs, check함수 활용방법, 문자열을 배열처럼 활용하는방법

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

프로그래머스

1. 문자열을 배열처럼 활용하는방법

auto place : places
후
place[i][j]로 접근하면 된다.

places -> [POOOX, PPPPP..], [PPAP, ...] [...]
place -> [POOOX, PPPPP, ...]
place[i] - > POOOX
place[i][0]=='P'

 

2. check함수 활용방법

1. check로 의사코드짜고
2. 이후에 구체적으로 구현하도록 하자

for(auto place : places){
        if(check(place)) answer.push_back(1); //지킴
        else answer.push_back(0); //안지킴
    }

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

int vis[5][5];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
vector<int> answer;
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;
    
}
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) {

    for(auto place : places){
        if(check(place)) answer.push_back(1); //지킴
        else answer.push_back(0); //안지킴
    }
    return answer;
}

 

* 25.5.8. 3회독

그려보면서 P에대해 검사범위를 파악

return문은 for문위에 선언할것.

자기자신 예외처리 주의.

import java.util.*;

class A{
    int y,x,dist;
    A(int y, int x, int dist){
        this.y=y;
        this.x=x;
        this.dist=dist;
    }
}

class Solution {
    
    static int[] dy={0,1,-1,0};
    static int[] dx={1,0,0,-1};
    
    boolean bfs(int yy, int xx, String[] place){
        Queue<A> q = new LinkedList<>();
        q.offer(new A(yy,xx,0));
        boolean[][] vis = new boolean[5][5];
        vis[yy][xx]=true;
        
        while(q.size()>0){
            A a = q.poll();
            int y = a.y;
            int x = a.x;
            int dist = a.dist;
            vis[y][x]=true;
            
            if(dist>2) continue;
            if(dist!=0 && place[y].charAt(x)=='P') return false; //return문은 for문위에, 시작점은 예외처리.
            
            for(int i=0;i<4;++i){
                int ny=y+dy[i];
                int nx = x+dx[i];
                if(ny<0 || nx<0 || ny>=5 || nx>=5) continue;
                if(vis[ny][nx]) continue;
                if(place[ny].charAt(nx)=='X') continue;
                // if(place[ny].charAt(nx)=='P') return false;
                q.offer(new A(ny,nx,dist+1));
            }
        }
        return true;
    }
    
    boolean go(String[] place){
        for(int i=0;i<5;++i){
            for(int j=0;j<5;++j){
                if(place[i].charAt(j)=='P'){
                    if(!bfs(i,j,place)){
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        // System.out.println(places[0][1]);
        
        int idx=0;
        for(String[] place : places){
            // System.out.println(place[0]);
            if(go(place)){
                answer[idx]=1;   
            }
            idx++;
        }
        return answer;
    }
}