[c++][프로그래머스] 거리두기 확인하기

프로그래머스 거리두기 확인하기 [2021 카카오 채용연계형 인턴십]
https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

문제 풀이

• 이 문제는 DFS로 풀었습니다. 
• 각 대기실 별로 사람이 있는 위치(P)에서 DFS 탐색을 시작해 거리가 2 이내에 다른 사람을 만나면 거리두기를 지키지 않은 대기실입니다. 
• 탐색을 할 때, 결과가 참이라면 모든 인원을 확인해야 하기 때문에 계속해서 탐색, 거짓이라면 바로 break 후 answer 벡터에 결과를 push 합니다. 

코드

#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; // 거리 2 이내에 사람 만나면 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)) { // 결과 거짓이면 바로 break, 참이면 계속 탐색
                        flag = false;
                        break;
                    }
                }
            }
        }
        
        answer.push_back(flag);
    }
    
    return answer;
}

실행 결과