거리두기 확인하기--C++

이번글은 이 글을 보고 만들었습니다.

쉬울줄 알고 연습장에 안썻다가 머리가 꼬여, 아에 풀지 못한문제...

DFS를 사용하는 문제였습니다.

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int p=0;p<N;p++){
        bool flag = true;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(places[p][i][j]=='P'){
                    memset(visit,0,sizeof(visit));
                    visit[i][j]=1;
                    if(!dfs(places[p],i,j,0)){
                        flag =false;
                        break;
                    }
                }
            }
            if(!flag) break; //내가 추가한부분
        }
        answer.push_back(flag);
    }
    return answer;
}

강의실이 5개로 정해졌으므로, 각 강의실을 돌면서 확인할것입니다.
P부터 시작을 합니다. -> 여기서 visited를 1로 만들고 넘겨줘야합니다.
dfs에서 false가 나오면 flag를 false로 바꾸고 break합니다.

if(!flag) break는 참고 블로그에는 없는 글인데, break를 for문내에걸면 가장 가까운 for이 빠져나갑니다. 고로, 한명이라도 거리두기를 안지켰다면 다른것도 살펴볼 이유가 없으므로 break문을 걸었습니다.

bool dfs(vector<string> &place,int y,int x,int count){
    if(count>=3) return true;
    if(count > 0 && place[y][x] =='P') return false;
    
    for(int d=0;d<4;d++){
        int ny = y +dy[d];
        int nx = x+dx[d];
        if(!safe(ny,nx) || visit[ny][nx]) continue;
        if(place[ny][nx]=='X') continue;
        
        visit[ny][nx] = 1;
        if(!dfs(place,ny,nx,count+1)) return false;
        
        visit[ny][nx]=0;
    }
    return true;
}

count>=3을 넘어가면 P를 만나도 거리두기를 지켰으므로 더이상 확인할 필요가 없어 true를 반환합니다.

만약에 count가 0이상인데 P를 만났다 -> 거리두기를 지키지 않았으므로 false를 return합니다.

for문을 돌며 방문한 지점인지, 강의실을 벗어나지 않는지 확인합니다.
'x'면 continue로 넘어갑니다.

여기서 중요한점은 dfs한 뒤에 visit[ny][nx]=0으로 만들어줘서 다른 P에서 시작할때 막히지 않게 하는것입니다.
p
0
0
P
이때 맨위에서 시작하면
p
x visit
x
P
이고
하단 P에서 상단 P로 O로 열려있지만 visit했기때문에 갈수가 없습니다.
그래서 Backtracking처럼 dfs완료시 다시 방문할수있게 돌려놔야합니다.

최종코드

#include <string>
#include <vector>
#include <cstring>

using namespace std;

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

int visit[5][5];

bool safe(int y, int x) {
    return y>=0 && x>=0 && y<N && x<N; 
}

bool dfs(vector<string> &place,int y,int x,int count){
    if(count>=3) return true;
    if(count > 0 && place[y][x] =='P') return false;
    
    for(int d=0;d<4;d++){
        int ny = y +dy[d];
        int nx = x+dx[d];
        if(!safe(ny,nx) || visit[ny][nx]) continue;
        if(place[ny][nx]=='X') continue;
        
        visit[ny][nx] = 1;
        if(!dfs(place,ny,nx,count+1)) return false;
        
        visit[ny][nx]=0;
    }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int p=0;p<N;p++){
        bool flag = true;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(places[p][i][j]=='P'){
                    memset(visit,0,sizeof(visit));
                    visit[i][j]=1;
                    if(!dfs(places[p],i,j,0)){
                        flag =false;
                        break;
                    }
                }
            }
            if(!flag) break;
        }
        answer.push_back(flag);
    }
    return answer;
}