[JAVA 문제 풀이] 394. 거리두기 확인하기

내가 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];

        for (int i = 0; i < places.length; i++) {
            List<int[]> list = new ArrayList<>();

            // P 찾기 >> 찾으면 위치 리스트에 저장
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    if (places[i][j].charAt(k) == 'P') {
                        list.add(new int[] { j, k });
                    }
                }
            }

            // P가 없는 경우
            if (list.size() == 0) {
                answer[i] = 1;
                continue;
            }

            boolean isSafe = true;

            // 테이블 간 거리 확인
            for (int j = 0; j < list.size(); j++) {
                for (int k = j + 1; k < list.size(); k++) {
                    int[] p1 = list.get(j);
                    int[] p2 = list.get(k);
                    int dist = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]); // 두 테이블 간 거리

                    // 거리가 2 이하인 경우
                    if (dist <= 2) {
                        if (!isBlocked(p1, p2, places[i], dist)) {
                            isSafe = false;
                            break;
                        }
                    }
                }

                if (!isSafe) {
                    break;
                }
            }

            answer[i] = isSafe ? 1 : 0;
        }

        return answer;
    }

    // 두 테이블 간 거리가 2 이하인 경우
    // 사이에 X가 있는지 확인하는 메서드
    private boolean isBlocked(int[] p1, int[] p2, String[] place, int dist) {
        int r1 = p1[0];
        int c1 = p1[1];
        int r2 = p2[0];
        int c2 = p2[1];

        // 맨해튼 거리 1 >> 무조건 안 막혀 있음 (바로 붙어있음)
        if (dist == 1){
            return false;
        }

        // 같은 행 (좌우 2칸 차이)
        if (r1 == r2) {
            int mid = (c1 + c2) / 2;
            return place[r1].charAt(mid) == 'X';
        }

        // 같은 열 (상하 2칸 차이)
        if (c1 == c2) {
            int mid = (r1 + r2) / 2;
            return place[mid].charAt(c1) == 'X';
        }

        // 대각선 (1칸씩 차이)
        return place[r1].charAt(c2) == 'X' && place[r2].charAt(c1) == 'X';
    }
}

다른 사람의 코드

class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visit;

    static int[] answer;

    public void dfs(int num, int x, int y, int count, String[] places){
        if (count > 2) return;
        if (count > 0 && count <= 2 && places[x].charAt(y) == 'P'){
            //2칸 범위내에 다른 응시자가 있을 경우 거리두기 미준수로 0처리
            answer[num] = 0;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            //배열 범위 밖으로 초과하는지 여부 검사, 파티션으로 분리되어 있는 경우 상관 없음.
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && places[nx].charAt(ny) != 'X') {
                if (visit[nx][ny]) continue; //이미 방문한 곳일 경우 생략
                visit[nx][ny] = true;
                dfs(num, nx, ny, count + 1, places);
                visit[nx][ny] = false;
            }
        }
    }

    public int[] solution(String[][] places) {
        answer = new int[places.length];
        for (int i = 0; i < places.length; i++) {
            answer[i] = 1;
        }

        for (int i = 0; i < places.length; i++) {
            visit = new boolean[5][5];
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    if (places[i][j].charAt(k) == 'P'){
                        visit[j][k] = true;
                        dfs(i, j, k, 0, places[i]);
                        visit[j][k] = false;
                    }
                }
            }
        }
        return answer;
    }
}