거리두기 확인하기

문제 링크

[프로그래머스] 거리두기 확인하기

문제 풀이

문제 설명

각 응시자들 간의 맨해튼 거리가 2 이하인 응시자들이 있는지를 확인하는 문제이다. 단, 파티션으로 막혀있다면 맨해튼 거리상 2 이하에 있더라도 상관없다.

문제 접근 방식

대기실은 총 5개이며 각 대기실 크기는 5 x 5이다.

단순하게 접근하면 각 응시자들 간의 거리를 구하고 그 사이에 파티션이 있는지 체크하면 될 거라고 판단했다.

파티션으로 막히는 경우는 ‘PXP’처럼 응사자들 사이에 파티션이 있는 경우밖에 존재하지 않기 때문이다.

단, 대각선 방향에 있는 경우 2가지 경우의 수를 고려해야한다.

문제 1

해당 방식을 고려한 코드는 아래와 같으나, 몇몇 테스트케이스에서 에러가 발생했다.

import java.util.*;
class Solution {
    // 맨해튼 거리 계산 함수
    public int manhattan(int[] start, int[] end) {
        int y = Math.abs(start[0] - end[0]);
        int x = Math.abs(start[1] - end[1]);
        return y + x;
    }
    // 접근 가능한지 확인하는 함수
    public boolean canGo(char[][] map, int[] start, int[] end) {
        // 거리가 1이면 true 반환
        if (manhattan(start, end) == 1)
            return true;
        // 거리가 2일 경우 파티션 계산
        int y1 = start[0];
        int y2 = end[0];
        int x1 = start[1];
        int x2 = end[1];
        if (y1 == y2) {
            int mid = (x1 + x2) / 2;
            return map[y1][mid] != 'X';
        }
        if (x1 == x2) {
            int mid = (y1 + y2) / 2;
            return map[mid][x1] != 'X';
        }
        // 대각선인 경우
        return map[y1][x2] != 'X' && map[y2][x1] != 'X';
    }
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        Arrays.fill(answer, 1);
        for (int T = 0; T < 5; T++) {
            String[] place = places[T];
            char[][] map = new char[5][5];
            List<int[]> part = new ArrayList<>();
            // map 할당 및 응시자 위치 할당
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[i][j] = place[i].charAt(j);
                    if (map[i][j] == 'P') {
                        part.add(new int[] {i, j});
                    }
                }
            }
            // 응시자 간 맨해튼 거리 계산
            for (int i = 0; i < part.size(); i++) {
                for (int j = i + 1; j < part.size(); j++) {
                    // 맨해튼 거리 <= 2라면 파티션 여부 파악
                    int[] start = part.get(i);
                    int[] end = part.get(j);
                    if (manhattan(start, end) <= 2) {
                        if (canGo(map, start, end)) {
                            answer[T] = 0;
                        }
                    }
                }
            }
            
        }
        return answer;
    }
}

이유는 대각선일 경우 파티션 유무 조건식이 잘못된 것이 문제였다. // return map[y1][x2] != 'X' && map[y2][x1] != 'X';

문제를 금방 파악해서 수정할 수 있었다.

최종 코드

최종 코드는 아래와 같다.

import java.util.*;
class Solution {
    // 맨해튼 거리 계산 함수
    public int manhattan(int[] start, int[] end) {
        int y = Math.abs(start[0] - end[0]);
        int x = Math.abs(start[1] - end[1]);
        return y + x;
    }
    // 접근 가능한지 확인하는 함수
    public boolean canGo(char[][] map, int[] start, int[] end) {
        // 거리가 1이면 true 반환
        if (manhattan(start, end) == 1)
            return true;
        // 거리가 2일 경우 파티션 계산
        int y1 = start[0];
        int y2 = end[0];
        int x1 = start[1];
        int x2 = end[1];
        if (y1 == y2) {
            int mid = (x1 + x2) / 2;
            return map[y1][mid] != 'X';
        }
        if (x1 == x2) {
            int mid = (y1 + y2) / 2;
            return map[mid][x1] != 'X';
        }
        // 대각선인 경우
        return map[y1][x2] != 'X' || map[y2][x1] != 'X';
    }
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        Arrays.fill(answer, 1);
        for (int T = 0; T < 5; T++) {
            String[] place = places[T];
            char[][] map = new char[5][5];
            List<int[]> part = new ArrayList<>();
            // map 할당 및 응시자 위치 할당
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[i][j] = place[i].charAt(j);
                    if (map[i][j] == 'P') {
                        part.add(new int[] {i, j});
                    }
                }
            }
            // 응시자 간 맨해튼 거리 계산
            for (int i = 0; i < part.size(); i++) {
                for (int j = i + 1; j < part.size(); j++) {
                    // 맨해튼 거리 <= 2라면 파티션 여부 파악
                    int[] start = part.get(i);
                    int[] end = part.get(j);
                    if (manhattan(start, end) <= 2) {
                        if (canGo(map, start, end)) {
                            answer[T] = 0;
                        }
                    }
                }
            }
            
        }
        return answer;
    }
}