프로그래머스 거리두기 확인하기 81302 Java (level 2)

2021 카카오 채용연계형 인턴십

 

문제 요약

5개의 5x5 대기실에서 응시자들이 코로나19 방역 수칙에 맞게 거리두기를 준수했는지 확인하여, 각 대기실에 대해 거리두기가 지켜졌으면 1, 그렇지 않으면 0을 반환.

 

• 규칙:
  • 응시자(P) 간 맨해튼 거리가 2 이하가 되면 안 됩니다.
  • 단, 예외:
    • P 사이에 파티션(X)이 있다면 거리두기를 지킨 것으로 간주.
    • 빈 테이블(O)이 있더라도 P가 맨해튼 거리 2 이하로 배치된 경우는 거리두기 미준수.
• 입력:
  • places: 5개의 대기실을 나타내는 2차원 문자열 배열 (각 대기실은 5x5 크기).
• 출력:
  • 거리두기가 지켜졌다면 1, 한 명이라도 지키지 않았다면 0을 1차원 배열로 반환.
    예: [1, 0, 1, 1, 1]
• 제약사항:
  • 각 대기실의 크기는 항상 5x5.
  • 각 자리에는 다음 중 하나가 표시됨:
    • P: 응시자가 앉아있는 자리
    • O: 빈 테이블
    • X: 파티션
• 맨해튼 거리 계산 공식:
  두 좌표 (r1, c1)와 (r2, c2) 간의 거리 = |r1 - r2| + |c1 - c2|

 

접근 방식

맨해튼거리가 2이하라는 것은 격자라는 것에 한해서 보면, 다음칸에 해당한다.

따라서 응시자들 간 거리는 따질 때 상하좌우, 대각선으로 나누어서 생각해보았다.

상하좌우 같은 경우는 p와 가까운 칸이 x 고 그 다음 칸에 위치한 p 인 case를 빼고는 주위에 p가 있다면 불가능한 case다.

대각선같은경우는 P에서 대각선으로 가는 방법(2가지)에 대해서 파티션이 있는지 체크해주고 그렇지않으면 불가능한 case라고 생각했다.

배열의 크기가 워낙 작다보니, 엣지 case가 있지 않아보인다

 

 

작성한 코드는 다음과 같다 ☺️

import java.util.*;

class Solution {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int[] diagonalx = {1,1,-1,-1};
    static int[] diagonaly = {-1,1,1,-1};
    public int[] solution(String[][] places) {
        int[] answer = new int [5];
        for(int k =0 ;k<5;k++){
            char[][] arr = new char[5][5];
            Queue<int[]> que = new ArrayDeque<>();
            for(int j=0;j<5;j++){
                String p= places[k][j];
                for(int i =0;i<5;i++){
                    char c = p.charAt(i);
                    arr[i][j] =c;
                    if(c=='P'){
                        que.add(new int[] {i,j});
                    }
                }
            }
            answer[k]= dfs(arr,que);
        }
        return answer;
    }
    
    public int dfs(char[][] arr, Queue<int[]> que){
        while(!que.isEmpty()){
            int[] q = que.poll();
            int x = q[0];
            int y =q[1];
            for(int di =0; di<4;di++){
                int sx = diagonalx[di]+x;
                int sy = diagonaly[di]+y;
                if(sx<0 || sy<0 || sx>=5 ||sy>=5) continue;
                if(arr[sx][y]=='X' && arr[x][sy]=='X') continue;
                if(arr[sx][sy]=='P') return 0;
            }
            for(int di =0; di<4;di++){
                int sx = dx[di]+x;
                int sy = dy[di]+y;
                int tx = dx[di]*2+x;
                int ty = dy[di]*2+y;
                if(sx<0 || sy<0 || sx>=5 ||sy>=5) continue;
                if(arr[sx][sy]=='P') return 0;
                if(tx<0 || ty<0 || tx>=5 ||ty>=5) continue;
                //칸막이가 적용 되는 경우
                if(arr[sx][sy]=='X' && arr[tx][ty]=='P') continue;
                if(arr[tx][ty]=='P') return 0;
            }
        }
        return 1;
    }
}

 

 

Eug2n2's GitHub