프로그래머스 : 거리두기 확인하기(C++)

문제

풀이

이 문제는 그래프와 DFS를 이용해서 풀었습니다.
각 지점에서 인접한 지점은 총 4개입니다.
처음 'P'인 지점만 DFS를 호출해주었고 인접한 지점이 'O'이면 DFS를 재귀적으로 호출해주었습니다.
(depth 변수를 이용해서 맨해튼거리가 2이하인 지점까지만 DFS를 호출해주었습니다.)

DFS를 하면서 'P'를 만나면 flag값을 false로 바꾸어주었습니다.
이를 이용해서 문제를 해결했습니다.

코드

#include <string>
#include <vector>
#include<cstring>
#include <iostream>
using namespace std;

bool flag;
bool visited[5][5];
int x[4] = {-1, 0, 0, 1};
int y[4] = {0, 1, -1, 0};
vector<vector<string>> place;

void DFS(int o, int i, int j, int depth) {
    visited[i][j] = true;
    depth++;
    
    for(int k = 0; k < 4; k++) {
        int i_ = i + y[k];
        int j_ = j + x[k];

        if(i_ < 0 || j_ < 0 || i_ >= 5 || j_ >= 5) {
            continue;
        }
        
        if(place[o][i_][j_] == 'X') {
            continue;
        }
        
        if(visited[i_][j_] == true) {
            continue;
        }
        
        if(place[o][i_][j_] == 'P') {
            flag = false;
        }
        
        if(place[o][i_][j_] == 'O' && depth < 2) {
            DFS(o, i_, j_, depth);
        }
    }
}
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    place = places;
    // 대기실 별
    for(int i = 0; i < 5; i++) {

        bool check = false;
        memset(visited,false,sizeof(visited));
        flag = true;
        
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                if(visited[j][k] == false && place[i][j][k] == 'P') {


                    DFS(i, j, k, 0);
                    if(flag == false) {
                        check = true;
                        break;
                    }
                }
            }
        }
        if(check == true) {
            answer.push_back(0);
        }
        else {
            answer.push_back(1);
        }
    }
    return answer;
}