거리두기 확인하기(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

대기실별로 맨해튼 거리가 2 이하인 응시자가 있는지 확인(단, 파티션이 막고 있는 경우 제외)

 

---

 

풀이

 

접근 방식

1. 응시자들의 맨해튼 거리가 1인 경우

  → false 리턴

 

2. 응시자들의 맨해튼 거리가 2인 경우

  → 같은 방향으로 두 칸 떨어져 있는 경우 응시자들 사이에 빈 공간(O)이 있다면 false

  → 대각선으로 떨어져 있는 경우 응시자의 (위쪽, 왼쪽)  / (위쪽, 오른쪽) / (아래쪽, 왼쪽) / (아래쪽, 오른쪽) 위치에 빈 공간(O)이 있다면 false

 

---

 

코드리뷰

 

import java.util.*;

class Solution {
    int N, M;
    String[][] maps;
    
    // 상하좌우 한 칸씩 탐색을 위한 배열
    int[] dirY1 = {-1, 1, 0, 0};
    int[] dirX1 = {0, 0, -1, 1};
    
    // 상하좌우 두 칸씩 탐색을 위한 배열
    int[] dirY2 = {-2, 2, 0, 0};
    int[] dirX2 = {0, 0, -2, 2};
    
    // 대각선 탐색을 위한 배열
    int[] dirY3 = {-1, -1, 1, 1};
    int[] dirX3 = {-1, 1, -1, 1};

    // 대기실 map 구성 메소드
    public String[][] makeMap(String[] arr) {
        this.N = arr.length;
        this.M = arr[0].length();
        
        // 두 칸씩 떨어져 있는 경우를 확인할 때 맵을 벗어나는 것을 방지하기 위해 크기는 +4로 설정
        String[][] tempMap = new String[N+4][M+4];
        for(int i = 0; i < tempMap.length; i++) {	// map의 크기만큼 X로 채우기
            for(int j = 0; j < tempMap.length; j++) {
                tempMap[i][j] = "X";
            }
        }
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                char c = arr[i].charAt(j);
                if(c == 'P') tempMap[i+2][j+2] = "P";	// 응시자 표시
                else if(c == 'O') tempMap[i+2][j+2] = "O";	// 빈 공간 표시
            }
        }
        return tempMap;
    }

    // 맨해튼 거리가 1인 응시자 확인
    public boolean check1(String[][] map) {
        for(int i = 2; i < N+2; i++) {	// 탐색의 시작 좌표는 (2, 2)
            for(int j = 2; j < M+2; j++) {
                if(map[i][j].equals("P")) {
                    for(int k = 0; k < 4; k++) {
                        int row = i + dirY1[k];
                        int col = j + dirX1[k];
                        if(map[row][col].equals("P")) {	// 상하좌우에 응시자(P)가 존재한다면
                            return false;	// false 리턴
                        }
                    }
                }
            }
        }
        return true;
    }

    // 맨해튼 거리가 2인 응시자 확인(같은 방향으로)
    public boolean check2(String[][] map) {
        for(int i = 2; i < N+2; i++) {
            for(int j = 2; j < M+2; j++) {
                if(map[i][j].equals("P")) {
                    for(int k = 0; k < 4; k++) {
                        int row1 = i + dirY1[k];
                        int col1 = j + dirX1[k];
                        int row2 = i + dirY2[k];
                        int col2 = j + dirX2[k];
                        
                        // 두 칸 떨어져 있는 곳에 응시자(P)가 있고, 그 사이가 빈공간(O)이라면
                        if(map[row2][col2].equals("P") && map[row1][col1].equals("O")) {
                            return false;	// false 리턴
                        }
                    }
                }
            }
        }
        return true;
    }

    // 맨해튼 거리가 2인 응시자 확인(대각선 방향으로)
    public boolean check3(String[][] map) {
        for(int i = 2; i < N+2; i++) {
            for(int j = 2; j < M+2; j++) {
                if(map[i][j].equals("P")) {
                    for(int k = 0; k < 4; k++) {
                        int row3 = i + dirY3[k];
                        int col3 = j + dirX3[k];
                        if (map[row3][col3].equals("P")) {	// 대각선 방향에 응시자(P)가 있는 경우
                            if (k == 0) {	// (위쪽, 왼쪽) 대각선 방향의 경우
                                if (map[i - 1][j].equals("O") || map[i][j - 1].equals("O"))	// 위쪽이나 왼쪽이 빈공간(O)이면 false
                                    return false;
                            } else if (k == 1) {	// (위쪽, 오른쪽) 대각선 방향의 경우
                                if (map[i - 1][j].equals("O") || map[i][j + 1].equals("O"))	// 위쪽이나 오른쪽이 빈공간(O)이면 false
                                    return false;
                            } else if (k == 2) {	// (아래쪽, 왼쪽) 대각선 방향의 경우
                                if (map[i + 1][j].equals("O") || map[i][j - 1].equals("O"))	// 아래쪽이나 왼쪽이 빈공간(O)이면 false
                                    return false;
                            } else if (k == 3) {	// (아래쪽, 오른쪽) 대각선 방향의 경우
                                if (map[i + 1][j].equals("O") || map[i][j + 1].equals("O"))	// 아래쪽이나 오른쪽이 빈공간(O)이면 false
                                    return false;
                            }
                        }
                    }
                }
            }
        }
        return true;
    }

    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        for(int i = 0; i < places.length; i++) {
            maps = makeMap(places[i]);	// 각 대기실마다 map 만들어서
            if(check1(maps) && check2(maps) && check3(maps)) {	// 거리두기 확인
                answer[i] = 1;	// 지키고 있다면 1
            } else {
                answer[i] = 0;	// 지키지 않고 있다면 0
            }
        }
        return answer;
    }
}

 

---

 

추가 자료

 

대기실의 +4 만큼의 크기로 map 설정

 

 

거리두기를 지키지 않은 경우