프로그래머스 - 거리두기 확인하기 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81302

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

 

 

풀이

배열을 순회하다 사람('P')이 있다면 DFS를 수행한다.

DFS의 종료 조건은 깊이가 2가 될동안 사람('P')을 만나지 않는다면 true를 리턴

만난다면 false를 리턴하며 범위를 벗어나거나, 이미 방문했거나, 막혀있다면('X') 계속 진행해준다. 

 

만약 DFS가 false를 리턴하면 거리두기를 지키지 못한 것이므로 bool 변수 fail을 통해

for문을 벗어나도록 해준다. 만약 fail이 false로 유지된다면 모두 거리두기를 지킨 것이므로 해당 인덱스에 +1을 해준다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

bool visited[5][5] = { false, };
int dy[4] = { 1, 0, -1, 0};
int dx[4] = { 0, 1, 0, -1};

bool isInside(int j, int k){
    if(j < 5 && k < 5 && j >= 0 && k >= 0) return true;
    else return false;
}

bool DFS(vector<string> place, int y, int x, int cnt){
    if(cnt > 2) return true;
    if(cnt > 0 && place[y][x] == 'P') return false;
    
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if(!isInside(ny, nx) || visited[ny][nx] || place[ny][nx] == 'X') continue;
        
        visited[ny][nx] = true;
        if(!DFS(place, ny, nx, cnt + 1)) return false;
        visited[ny][nx] = false;
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer(5, 0);
    
    for(int i=0; i<5; i++){
        bool fail = false;
        
        for(int j=0; j<5; j++){
            for(int k=0; k<5; k++){
                if(places[i][j][k] == 'P'){
                    memset(visited, false, sizeof(visited));
                    
                    visited[j][k] = true;
                    if(!DFS(places[i], j, k, 0)){
                        fail = true;
                        break;
                    }
                }
            }
            if(fail) break;
        }
        
        if(!fail) answer[i] += 1;
    }
    
    
    return answer;
}