거리두기 확인하기
문제 설명
-
(r1, c1), (r2, c2)일 때, 맨해튼 거리는 |r1-r2| + |c1-c2|이다.
한 응시지가 다른 응시자와 맨해튼 거리 안에 있다면 그것은 거리 두기를 지키지 못한 것이다. 그러나 그 사이에 파티션이 있다면 거리두기를 지킨 것이다.
만약, 맨해튼 거리가 2 이하인데 그 사이에 빈테이블이 있다면 거리두기를 지키지 못한 것이다. -
places에서 거리두기를 지킨 대기실은 1, 지키지 못한 대기실은 0을 반환한다.
시행착오 및 문제 풀이
풀이
-
위, 아래, 옆을 탐색하는 것이므로 bfs
-
대기실의 크기는 무조건 5x5 이므로 이중 for문 i,j는 5만큼씩 돈다. [i][j]가 P라면 거기서 탐색 시작.
2-1. 거리두기를 지켰다면 true이므로 check에 true 저장, 거리두기를 지키지 못했다면 false 저장
2-2. 한 대기실 다 돌고 난 후 check에 따라 answer에 0,1 넣은 후 반환 -
bfs
3-1. Queue에서 시작을 넣는다.
3-2. 4방향을 돌며 이동한다. 이때 범위를 벗어나거나 나 자신일 경우 패스
3-3. Math.abs를 활용하여 맨해튼 거리를 구한다.
3-4. 맨해튼 거리가 2보다 작거나 같고 이동한 곳에 다른 응시자가 있다면 거리두기 실패 = false 반환
3-5. 맨해튼 거리가 2보다 작고 이동한 곳이 빈자리이면 다시 탐색
오답 코드
//bfs
import java.util.*;
class Solution {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public int[] solution(String[][] places) {
int[] answer = new int[places.length];
int idx = 0;
for(String[] p:places) {
boolean check = false;
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
//P라면
if(p[i].charAt(j) == 'P') {
check = bfs(i,j,p);
}
}
}
//거리두기를 지켰다면
if(check) {
answer[idx] = 1;
}
else {
answer[idx] = 0;
}
idx++;
}
return answer;
}
public boolean bfs(int x, int y, String[] p) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while(!q.isEmpty()) {
int[] temp = q.poll();
int now_x = temp[0];
int now_y = temp[1];
for(int i=0; i<4; i++) {
int next_x = now_x + dx[i];
int next_y = now_y + dy[i];
//범위를 벗어나거나 이미 갔던 곳이면 패스
if(next_x<0 || next_x>=5 || next_y<0 || next_y>=5) {
continue;
}
//맨해튼 거리
int m = Math.abs(next_x-now_x) + Math.abs(next_y-now_y);
//맨해튼 거리가 2보다 작고 이동한 곳에 다른 응시자가 있으면 거리두기 실패
if(m < 2 && p[next_x].charAt(next_y) == 'P') {
return false;
}
//맨해튼 거리가 2보다 작고 이동한 곳이 빈자리이면 거기서부타 재탐색
if(m < 2 && p[next_x].charAt(next_y) == 'O') {
q.add(new int[]{next_x, next_y});
}
}
}
//거리두기 지킴
return true;
}
}테스트 1
입력값 〉 [["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]
실행 결과 〉 실행한 결괏값 [1,0,0,0,1]이 기댓값 [1,0,1,1,1]과 다릅니다.
테스트 결과 (~˘▾˘)~
1개 중 0개 성공오답 이유
총 3가지가 틀렸다.
1. check
if(p[i].charAt(j) == 'P') {
check = bfs(i,j,p);
}check가 무조건 마지막 값으로만 갱신된다.
그러므로 한 부분이라도 거리두기를 못지킨 부분이 나온다면 false가 되고 끝나야 한다.
- 나 자신 패스하지 않음
if(next_x<0 || next_x>=5 || next_y<0 || next_y>=5) {
continue;
}나 자신을 패스하지 않았다.
만약 (0,0)에서 (0,1)을 탐색했을 때, (0,1)에서 다시 탐색할 수 있는데, 이때 (0,0)이 P라면 나 자신이지만 거리두기를 실패했다고 판단한다. 그러므로 시작점 제외
- 맨해튼 거리
int m = Math.abs(next_x-now_x) + Math.abs(next_y-now_y);맨해튼 거리는 시작점에서부터 다음 자리까지의 거리를 구해야 한다. 그러므로 now_x, now_y가 아니라 x,y이다.
즉, 지금 탐색을 하고 있는 장소가 아닌 애초에 시작한 곳에서부터 거리를 구해야 한다는 뜻~!
오답 코드
//bfs
import java.util.*;
class Solution {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public int[] solution(String[][] places) {
int[] answer = new int[places.length];
int idx = 0;
for(String[] p:places) {
boolean check = true;
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
//P라면
if(p[i].charAt(j) == 'P') {
//한 부분이라도 거리두기를 지키지 못했다면 0
if(!bfs(i,j,p)) {
check = false;
break;
}
}
}
}
//거리두기를 지켰다면
if(check) {
answer[idx] = 1;
}
else {
answer[idx] = 0;
}
idx++;
}
return answer;
}
public boolean bfs(int x, int y, String[] p) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while(!q.isEmpty()) {
int[] temp = q.poll();
int now_x = temp[0];
int now_y = temp[1];
for(int i=0; i<4; i++) {
int next_x = now_x + dx[i];
int next_y = now_y + dy[i];
//범위를 벗어나거나 나 자신 패스
if(next_x<0 || next_x>=5 || next_y<0 || next_y>=5 || (next_x==x && next_y==y)) {
continue;
}
//맨해튼 거리
int m = Math.abs(next_x-x) + Math.abs(next_y-y);
//맨해튼 거리가 2보다 작고 이동한 곳에 다른 응시자가 있으면 거리두기 실패
if(m < 2 && p[next_x].charAt(next_y) == 'P') {
return false;
}
//맨해튼 거리가 2보다 작고 이동한 곳이 빈자리이면 거기서부터 재탐색
if(m < 2 && p[next_x].charAt(next_y) == 'O') {
q.add(new int[]{next_x, next_y});
}
}
}
//거리두기 지킴
return true;
}
}76.3..?
또 왜 틀렸지;;
오답 이유
//맨해튼 거리가 2보다 작고 이동한 곳에 다른 응시자가 있으면 거리두기 실패
if(m < 2 && p[next_x].charAt(next_y) == 'P') {
return false;
}
//맨해튼 거리가 2보다 작고 이동한 곳이 빈자리이면 거기서부터 재탐색
if(m < 2 && p[next_x].charAt(next_y) == 'O') {
q.add(new int[]{next_x, next_y});
}if(m <= 2 && p[next_x].charAt(next_y) == 'P') {
return false;
}
가 되어야 한다.
ex) POP인 경우 맨해튼 거리가 2이지만 중간이 빈자리이므로 거리두기 실패
POOP인 경우, P의 옆이 O이므로 첫번째 O부터 재탐색한다. 그 옆도 O이므로 재탐색하지만 맨해튼 거리가 2를 넘어섰으므로 조건에 부합하지 않는다. 거리두기를 지킨 것이다.
그러므로 두번째 if절은 2를 포함하지 않는다.
그냥 내 스스로 쉽게 생각해본건....
바로 옆에 P가 있는 경우는 조건에서 준 그대로 2이하이지만
그 옆이 O인 경우, 한번 경유를 하므로 2보다 작아야 한다.
정답 코드
//bfs
import java.util.*;
class Solution {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public int[] solution(String[][] places) {
int[] answer = new int[places.length];
int idx = 0;
for(String[] p:places) {
boolean check = true;
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
//P라면
if(p[i].charAt(j) == 'P') {
//한 부분이라도 거리두기를 지키지 못했다면 0
if(!bfs(i,j,p)) {
check = false;
break;
}
}
}
}
//거리두기를 지켰다면
if(check) {
answer[idx] = 1;
}
else {
answer[idx] = 0;
}
idx++;
}
return answer;
}
public boolean bfs(int x, int y, String[] p) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while(!q.isEmpty()) {
int[] temp = q.poll();
int now_x = temp[0];
int now_y = temp[1];
for(int i=0; i<4; i++) {
int next_x = now_x + dx[i];
int next_y = now_y + dy[i];
//범위를 벗어나거나 나 자신 패스
if(next_x<0 || next_x>=5 || next_y<0 || next_y>=5 || (next_x==x && next_y==y)) {
continue;
}
//맨해튼 거리
int m = Math.abs(next_x-x) + Math.abs(next_y-y);
//맨해튼 거리가 2보다 작고 이동한 곳에 다른 응시자가 있으면 거리두기 실패
if(m <= 2 && p[next_x].charAt(next_y) == 'P') {
return false;
}
//맨해튼 거리가 2보다 작고 이동한 곳이 빈자리이면 거기서부터 재탐색
if(m < 2 && p[next_x].charAt(next_y) == 'O') {
q.add(new int[]{next_x, next_y});
}
}
}
//거리두기 지킴
return true;
}
}정답!!! 와 진짜 힘겨웠다;;;;;
