[c++/알고리즘] 프로그래머스 거리두기확인하기 (정확도 88.8-> 풀었다..!)

https://programmers.co.kr/learn/courses/30/lessons/81302

조건 접근

• 'P'에서 1만큼 위,아래,왼,오로 이동하였을 경우 'P'이면 그 강의실은 거리두기 위반
• 'P'에서 1만큼 위,아래,왼,오로 이동하였을 경우 'O'이고, 다시 'O'인 위치에서 1만큼 위,아래,왼,오로 이동하였을 경우 'P'인 경우 맨해튼거리가 2 이하이므로 강의실은 거리두기 위반

풀고나니 많이 지저분하다.

// 정답 코드
#include <string>
#include <vector>
#include <queue>

using namespace std;
int x, y;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int ddx, ddy, ddx1, ddy1;
int chk=0;
queue<pair<int,int>> q;

int ch_queue(char map[6][6], int ch[6][6]){

        while(!q.empty()){
        // queue에 담긴 원소를 꺼낸뒤, 해당 위치를 방문했으니 체크한다.
            x = q.front().first;
            y = q.front().second;
            q.pop();
            ch[x][y]=1;
			
            // 'P'에서 앞,뒤,위, 아래로 체크
            for(int m=0; m<=3; m++){
                ddx = x+dx[m];
                ddy = y+dy[m];
				
                // 범위를 벗어날 경우 continue
                if(ddx<0 || ddx > 5|| ddy< 0|| ddy>5) continue;
		// 이동한 위치가 'P'이고 해당 위치에 방문한 상태가 아니라면 거리두기 위반을 한 상태이므로 return 1;
                if(map[ddx][ddy] == 'P' && ch[ddx][ddy] == 0){
                    return 1;
                }
                // 이동한 위치가 'O'이고, 'O'에서 다시 앞,뒤,위,아래 체크해서 이동한 거리가 'P'이고, 방문한 상태가 아니라면 거리두기 위반으로 return 1;
                else if (map[ddx][ddy] == 'O'){
                    for(int n=0; n<=3; n++){
                        ddx1 = ddx+dx[n];
                        ddy1 = ddy+dy[n];
                        if(ddx1<0 || ddx1 > 5|| ddy1< 0|| ddy1>5) continue;

                        if(map[ddx1][ddy1] == 'P' && ch[ddx1][ddy1] == 0){
                            return 1;
                        }
                    }
                }
            }
        }

    return 0;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;

    for(int i=0; i<places.size(); i++){
        char map[6][6] = {0,};
        int ch[6][6] = {0,};
        for(int j=0; j<places.size(); j++){
            for(int k=0; k<places.size(); k++){
            	// 2차원 배열의 형태로 배치한다.
                map[k][j] = places[i][j][k];
                // 'P' 응시자가 앉아 있는 경우, queue에 넣는다.
                if(map[k][j] == 'P') {q.push(make_pair(k,j));}
            }
        }
	
    // q가 비어있으면, 응시자가 한명도 없는 경우(거리두기를 지키고 있느 경우)엔 1을 입력
    if(q.empty()){ answer.push_back(1); continue;}

    // ch_queue 함수 체크
    if(ch_queue(map, ch)==1){answer.push_back(0);}
    else if(ch_queue(map, ch)==0) answer.push_back(1);
    
    q = queue<pair<int,int>>();   
    }

    return answer;
}

---

// 정확도 88.8 인 풀이
#include <string>
#include <vector>
#include <queue>

using namespace std;
int x, y;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int ddx, ddy, ddx1, ddy1;
int chk=0;
queue<pair<int,int>> q;

int ch_queue(char map[6][6], int ch[6][6]){
    
        while(!q.empty()){
            x = q.front().first;
            y = q.front().second;
            q.pop();
            ch[x][y]=1;
                
            for(int m=0; m<=3; m++){
                ddx = x+dx[m];
                ddy = y+dy[m];
                
                if(ddx<0 || ddx > 5|| ddy< 0|| ddy>5) continue;
                if(map[ddx][ddy] == 'P'){
                    return 1;
                }
                else if (map[ddx][ddy] == 'O'){
                    for(int n=0; n<=3; n++){
                        ddx1 = ddx+dx[n];
                        ddy1 = ddy+dy[n];
                        if(ddx1<0 || ddx1 > 5|| ddy1< 0|| ddy1>5) continue;
                        
                        if(map[ddx1][ddy1] == 'P' && ch[ddx1][ddy1] == 0){
                            return 1;
                        }
                    }
                }
            }
        }
    
    return 0;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int i=0; i<places.size(); i++){
        char map[6][6];
        int ch[6][6];
        for(int j=0; j<places.size(); j++){
            for(int k=0; k<places.size(); k++){
                map[k][j] = places[i][j][k];
                if(map[k][j] == 'P') {q.push(make_pair(k,j));}
            }
        }
    
    if(q.empty()){ answer.push_back(1); continue;}
        
    if(ch_queue(map, ch)==1){answer.push_back(0);}
    else if(ch_queue(map, ch)==0) answer.push_back(1);
    q = queue<pair<int,int>>();   
    }
    
    return answer;
}