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

거리두기 확인하기

[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"],
["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"],
["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"],
["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"],
["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

P와 다른 P 사이 맨해튼 거리가 2 이하인지 확인해서 true or false 반환하는 문제이다. 이 때 그 중간에 'X'가 있으면 예외.

지금보면 단순한 dfs/bfs 문제인데 처음 봤을 때는
P 중심으로 다른 P 와 X 를 찾는 구현을 하는 방식을 생각했다.
탐색거리가 짧아서 그렇게 생각한 것 같다.
단순하게 dfs/bfs 하면서 카운트를 하면 되는 문제인데 실수했다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
using ii = pair<int,int>;

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

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

vector<int> solution(vector<vector<string>> places) {
    for(auto p : places){
        bool flag = true;

        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(p[i][j] == 'P'){
                    memset(visited,false,sizeof(visited));
                    visited[i][j] = true;
                    if(!dfs(p,i,j,0)){
                        flag=false;   
                        break;
                    };
                }
            }
        }
        answer.push_back(flag);
    }
    
    return answer;
}`