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

문제

풀이

#include <string>
#include <vector>
#include <string.h> // memset
using namespace std;
bool visited[5][5];

int dx[4];
int dy[4];
bool isSafe ;
void dfs(int y, int x, vector<string> place, int count){
    visited[y][x] = true;
    if(count>2 || place[y][x] == 'X') {
        return;
    }
    else {
        if(count !=0 && place[y][x] == 'P') {
            isSafe =false; 
            return;
        }
    
        for(int i=0; i<4; i++){
            int px = x+dx[i];
            int py = y+dy[i];
            if((px>=0&&py>=0) && (px<5 && py<5)){
                if(!visited[py][px]){
                    visited[py][px] = true;
                    dfs(py,px,place,count+1);
                    visited[py][px] = false; // 없애면 오류
                }
            }
        }
    }
}

//탐색으로 풀기
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    dx[0] = 1; dx[1] = 0; dx[2] = -1; dx[3] = 0;
    dy[0] = 0; dy[1] = 1; dy[2] = 0; dy[3] = -1;
    for(vector<string> place : places){
        isSafe = true;
        memset(visited, false, sizeof(visited));
        for(int y=0; y<5; y++){
            for(int x=0; x<5; x++){
               if(place[y][x] == 'P'){
                    dfs(y, x, place, 0);
                    if(!isSafe) break;
                } 
            }
            if(!isSafe) break;
        }
        isSafe==true?answer.push_back(1) : answer.push_back(0);
    }
    return answer;
}

 

해결 방법

 

1. 'P'를 발견하면 상하좌우로 깊이 탐색

2. 깊이 탐색을 돌고 그때마다 count를 세어주어 2 이상일 경우 (사람 간의 거리가 2 이상일 경우)와

    탐색 도중 'X'를 발경 할 경우(사람과 사람 사이에 칸막이가 있는 경우)는 조건을 만족하므로 제외

3. count가 2 미만이고, 'P'가 발견될 경우(사람 간의 사이가 2미터가 되지 않는 경우)

    return값으로 false를 주어 반복문을 빠져나온다.

4. false로 인해 반복문을 빠져나온 경우는 0을, 정상적으로 빠져나온 경우는 1을 정답배열에 삽입한다.

 

 

 

 

---

다른 사람 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

/*
"POOOP",
"OXXOX", 
"OPXPX",
"OOXOX",
"POXXP"
*/

bool is_valid_place(const vector<string>& place)
{
    constexpr size_t N = 5;

    vector<vector<int>> is_in_use(
        N,
        vector<int>(N, false)
    );

    int di[] = {1,-1,0,0};
    int dj[] = {0,0,1,-1};

    for(size_t i=0; i!=N; ++i)
        for(size_t j=0; j!=N; ++j)
            if(place[i][j] == 'P'){
                for(size_t k=0; k!=4; ++k){
                    size_t moved_i = i + di[k];
                    size_t moved_j = j + dj[k];

                    if(moved_i >= N || moved_j >= N)
                        continue;

                    switch(place[moved_i][moved_j]){
                        case 'P':
                            return false;
                        case 'O':
                            if(is_in_use[moved_i][moved_j])
                                return false;

                            is_in_use[moved_i][moved_j] = true;
                            break;
                        case 'X':
                            break;
                    }
                }
            }

    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer(5);
    for(size_t i=0; i!=5; ++i)
        answer[i] = is_valid_place(places[i]);
    return answer;
}

 

 

case 'O':
	if(is_in_use[moved_i][moved_j])
		return false;

	is_in_use[moved_i][moved_j] = true;
	break

이 부분이 이해가 가지 않았다가, 놀란 부분인데

이미 O주위에 사람이 있었다면, true로 바뀌었을 것이기 때문에

count를 세주지 않아도 주위에 P가 있다는 것(거리두기 수칙을 지키지 않은 것)을 알 수 있었다!

 

다른 사람들의 아이디어를 보는 건 정말 공부가 된다.