https://programmers.co.kr/learn/courses/30/lessons/81302#fn1
코딩테스트 연습 - 거리두기 확인하기
[["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"]] [1, 0, 1, 1, 1]
programmers.co.kr
거리두기를 만족하지 '않는' 경우
1. P가 이웃하여 위치할 때
2. P가 서로 대각선 위치에 위치하는 경우, 해당 대각선을 만드는 사각형에서 테이블이 하나라도 존재하는 경우 (그림 1 참고)
3. P가 서로 일직선에 위치하며, 위치 차이가 2인 경우, 둘 사이에 테이블이 존재하는 경우 (그림 2 참고)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <string>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
using namespace std;
//y,x
//상, 우, 하, 좌
vector<pair<int, int>> near = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
//대각선 & 상우하좌 간격 2
vector<pair<int, int>> dir = {{-1,-1}, {-1, 1}, {1, -1}, {1, 1},
{-2, 0}, {0, 2}, {2, 0}, {0, -2}};
//범위 검사
bool isValid(int row, int column)
{
return (row<5 && row>=0 && column<5 && column>=0);
}
bool checkMan(int r, int c, vector<string> p)
{
//거리두기 만족하지 않는 경우 1
for(int i=0;i<4;i++){
int nr = r + near[i].first;
int nc = c + near[i].second;
//사람 둘이 붙어있다면 거리두기 X이므로 false를 return
if(isValid(nr,nc) && (p[nr][nc]=='P')){
return false;
}
}
//대각선, 일직선 검사
for(int i=0;i<dir.size();i++){
int nr = r + dir[i].first;
int nc = c + dir[i].second;
if(!isValid(nr, nc) || p[nr][nc]!='P') continue;
//대각선과 일직선(거리 차 2) 좌표 중 값이 P인경우만 여기까지 들어옴. //거리두기 만족하지 않는 경우 2 if(abs(nr-r)==1||abs(nc-c)==1){
if(p[r][nc]=='O'||p[nr][c]=='O') return false;
}
//거리두기 만족하지 않는 경우 3 if(abs(nr-r)==2||abs(nc-c)==2){
if(nc<c && p[r][c-1]=='O') return false;
if(nc>c && p[r][c+1]=='O') return false;
if(nr<r && p[r-1][c]=='O') return false;
if(nr>r && p[r+1][c]=='O') return false;
}
}
//검사를 모두 통과하면 return true
return true;
}
vector<int> solution(vector<vector<string>> places) {
//5개의 대기실, 5*5크기
//맨해튼 거리가 3이상이어야 함.
//예외 : 자리 사이 파티션 존재 시 맨해튼 2여도 OK
//but, 사이에 빈 테이블이있는 경우는 X
// P: 응시자, O : 빈테이블, X: 파티션
//대기실 별로 거리두기 지키면 1 , 아니면 0
vector<int> answer;
for(int P=0;P<5;P++){//교실
int ans = 1;//지키는지 안지키는지. default : 지킨다.
for(int i=0;i<5;i++){//행
for(int j=0;j<5;j++){//열
if(places[P][i][j]=='P'){
if(!checkMan(i,j, places[P])){//P이면 주변 검사하러 보냄. false이면 지키지 못하므로
ans = 0;//ans을 0으로 세팅하고 그만.
break;
}
}
}
if(ans==0) break;
}
answer.push_back(ans);//한 교실 끝날때마다 ans값
}
return answer;
}
|
ㄱcs |
|
|
|
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 행렬 테두리 회전하기 / C++ (0) | 2021.11.12 |
|---|---|
| 프로그래머스 더 맵게 - C++, priority_queue로 min_heap 구성 (0) | 2021.11.11 |
| 프로그래머스 카카오프렌즈 컬러링북 - C++/ DFS (0) | 2021.11.11 |
| 프로그래머스 오픈채팅방 - C++, (unordered_map, sstream) (0) | 2021.11.11 |
| [C++] 베스트 앨범 (해시 문제) (0) | 2021.11.06 |