[PGM_81302] 거리두기 확인하기 (java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
브루트포스

이 문제는 5개의 방에 5x5로 자리가 있고, 그 자리마다 사람, 빈 의자, 파티션 중에 하나가 올 수 있다. 파티션을 기준으로 사람들은 붙어있을수 있지만, 빈 의자를 기준으로는 2칸이상 떨어져 있어야한다. 이 때 사람들이 모두 두 칸이상 떨어져 거리두기를 하고있는지 확인하는 문제이다.

파티션의 역할은 사람과 사람 사이의 거리를 2로 줄이는 기능을 한다. 즉 '사람 | 파티션 | 사람' 일 경우에는 거리두기를 하고 있는 것이다

하지만 빈 의자의 경우는 다르다. '사람 | 빈의자 | 사람' 의 경우 2칸이상 차이가 나지 않으므로 거리두기를 하고 있지 않은 상태가 된다. 

 

문제를 해결하기 위해 나는 재귀에 깊이를 더해 모든 경우의 수를 확인하여 체크하였다. 만약 특정 지점이 사람일 경우 상하좌우를 고려하여 사람이 있는지 확인하고, 없다면 다시 그 지점에서 상하좌우를 체크하여 사람이 있는지 확인하여 거리두기를 하는지 체크하였다. 이 때 파티션을 만나는 경우는 거리가 1이여도 괜찮기 때문에 사회적 거리두기를 하고있는 상황이라고 판단하였고, 다시한번 더 호출되는 경우는 빈 의자의 경우 다시 호출하여주었다. 체크하여주었다. 그리고 사람으로 인해 호출될 때마다, depth를 1 늘려주어 거리를 계산하여 주었다.

구현코드

package pgm_81302;

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

        for (int i = 0; i < 5; i++) {
            answer[i] = check(makePosition(places[i])) ? 1 : 0;
        }
        return answer;
    }

    private char[][] makePosition(String[] place) {
        char[][] positions = new char[5][5];

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                positions[i][j] = place[i].charAt(j);
            }
        }
        return positions;
    }

    public boolean check(char[][] positions) {
        boolean result = true;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (result) {
                    boolean[][] checked = new boolean[5][5];
                    result = isKeepDistance(positions, checked, i, j, 0);
                }
            }
        }
        return result;
    }

    public boolean isKeepDistance(char[][] positions, boolean[][] checked, int x, int y, int depth) {
        if (!(x < 5 && x >= 0 && y >= 0 && y < 5 && !checked[x][y]))
            return true;
        if (depth == 3)
            return true;
        if (positions[x][y] == 'P' && depth != 0)
            return false;

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        checked[x][y] = true;
        if (positions[x][y] == 'P') {
            for (int i = 0; i < dx.length; i++) {
                if (!isKeepDistance(positions, checked, x + dx[i], y + dy[i], depth + 1))
                    return false;
            }
        } else if (positions[x][y] == 'X')
            return true;
        else {
            if (depth == 0)
                return true;
            for (int i = 0; i < dx.length; i++) {
                if (!isKeepDistance(positions, checked, x+dx[i], y+dy[i], depth + 1))
                    return false;
            }
        }
        return true;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)