[프로그래머스][Level2][DFS][C++] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기 - 컴도리돌이.

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

 

1.  장소안에서 'P'가 나올 시 해당 i와 j 값에 대해서 방문 표시를 하고 DFS 탐색을 한다.
2.  DFS에서는 해당 문자열 벡터와 방문 bool 함수와 'P'의 좌표 마지막으로 deep이라는 매개변수를 받는다.
3.  deep은 말 그대로 DFS 탐색에서 최대 탐색 수 이다. (거리 두기의 거리를 2만큼 했기 때문에 deep 값이 2가 되면 return을 시킨다.)
4. 거리가 2가 안되었는데 도중에 'p'를 만난다면 거리두기를 하지 않았기 때문에 flag를 false를 시키고 return을 한다.
5.  flag가 false이면 answer에 0을 삽입한다.
6.  flag = false - > 거리두기 실패,  flag = true -> 거리두기 성공

#include <string>
#include <vector>

using namespace std;

const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
bool flag;
void check(vector<string>& p,vector<vector<bool>>& visited ,int x, int y,int deep)
{
    if(deep == 2) return;
    
    for(int i=0; i<4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 and ny >= 0 and nx <5 and ny < 5 and !visited[nx][ny] and p[nx][ny] != 'X')
        {
            if(p[nx][ny] == 'P')
            {
                flag = false;
                return ;
            }
            else
            {
                visited[nx][ny] = true;
                check(p,visited,nx,ny,deep+1);
            }
        }
    }
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(auto p : places)
    {
        vector<vector<bool>> visited(p.size(),vector<bool>(p.size(),false));
        flag = true;
        for(int i=0; i<p.size(); i++)
        {
            for(int j=0; j<p.size(); j++)
            {
                if(p[i][j] == 'P' and !visited[i][j])
                {
                    visited[i][j] = true;
                    check(p,visited,i,j,0);
                }
                
                if(!flag)
                {
                    answer.push_back(0);
                    break;
                }
            }
            if(!flag) break;
        }
        if(flag) answer.push_back(1);
    }
    return answer;
}