[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;
}
Author And Source
이 문제에 관하여([c++/알고리즘] 프로그래머스 거리두기확인하기 (정확도 88.8-> 풀었다..!)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@myeongs07/c알고리즘-프로그래머스-거리두기확인하기-정확도-88.8저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)