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

출처: 프로그래머스 코딩 테스트 연습 https://programmers.co.kr/learn/courses/30/lessons/81302

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

 

제출 날짜: 2021년 8월 31일 화요일

 

 

 

풀이

0. 이차원 배열 대기실을 하나씩 확인한다. 

1. 이때 P를 발견할 경우, P 자리를 방문했다고 표시한다.

2. 해당 자리(P 또는 O)의 주변(위 오른쪽 아래 왼쪽)을 확인한다.

    2-0. O의 주변 자리를 확인하려는데 방문했다고 표시되어 있다면 아래를 실행하지 않는다. P는 해당되지 않는다.

    2-1. P 주변에 P가 있을 경우 거리두기를 지키지 않는 것이기 때문에 끝낸다. O 주변에 P가 있어도 거리두기를 지키지 않는 것이기 때문에 끝낸다. P 때문에 O의 주변을 확인하는 것이기 때문이다.

    2-2. P 주변에 O가 있을 경우 2로 돌아간다. 만약 P가 아닌 O 때문에 주변을 확인 중이라면 주변에 O가 있는 것이 의미 없기 때문에 2-2는 실행하지 않는다.

3. 주변 확인이 모두 끝났으니, P 자리를 방문하지 않았다고 다시 표시하고 0으로 돌아간다.

 

 

 

생각

맨해튼 거리를 생각하면서 풀어야 하는 것 같은데 나는 거리를 따지지 않고 그림을 보고 풀었다.

문제 푸는데 시간이 오래 걸렸다. 우선 거리두기를 지키지 않는 false일 때 탐색 자체를 끝내지 않아서 문제가 발생했다. label 사용을 지양하려고 했는데 그냥 사용하는 게 편한 것 같다.

두번째로 P 때문에 O의 주변을 확인하는데 O의 주변에 다른 P가 아닌 해당 P가 발견될 경우 거리두기를 지키지 않는다고 인식하는 문제가 발생했다. 다음 질문글(https://programmers.co.kr/questions/19542)에 대한 답글로 문제점을 깨닫고 해결할 수 있었다.

마지막으로 나는 boolean[][] visited를 생각하지 못하고 방향을 int형 파라미터로 넘겨서 풀었는데 다른 사람의 풀이를 보고 더 깔끔하게 푸는 방법을 알게 되어 고쳤다.

 

 

 

코드

class Solution {   
    static int[][] d = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 위 오른쪽 아래 왼쪽
    static char[][] map;
    static boolean[][] visited;
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5]; // 답
        map = new char[5][5]; // 대기실
        visited = new boolean[5][5]; // 방문 여부

        for (int tc = 0; tc < places.length; tc++) {
            for (int i = 0; i < 5; i++) {
                map[i] = places[tc][i].toCharArray();
            }

            boolean keepingDistance = true; // 우선 거리두기하고 있다고 초기화
            checking: for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (map[i][j] == 'P') { // P일 경우
                        visited[i][j] = true; // 해당 위치는 방문했다고 체크 (O일 때 P라고 확인하지 않기 위함)
                        keepingDistance = checkNear(i, j, map[i][j]); // x,y좌표와 해당 자리
                        if (!keepingDistance) { // 주변 확인했는데 거리두기를 안 지키고 있다면 확인 끝내기
                            break checking;
                        }
                        visited[i][j] = false; // 다음 자리가 확인할 수 있도록 해당 위치 방문체크 해제
                    }
                }
            }
            answer[tc] = (keepingDistance) ? 1 : 0; // 거리두기 true면 1, false면 0
        }
        return answer;
    }
    
    private static boolean checkNear(int x, int y, char seat) { // xy좌표와 해당 자리에 있는 것
        for (int i = 0; i < 4; i++) {
            int dx = x + d[i][0];
            int dy = y + d[i][1];
            if (dx >= 0 && dx < 5 && dy >= 0 && dy < 5 && !visited[dx][dy]) { 
            // 대기실 내일 경우, 또 아직 방문하지 않았다면 확인하기 (방문한 경우: 맨 처음 확인하게 했던 P)
                if (map[dx][dy] == 'P') { // P가 있다면 false 리턴하고 끝
                    return false;
                } else if (map[dx][dy] == 'O' && seat == 'P') { // P 주변에 O가 있을 경우
                    boolean isPNear = checkNear(dx, dy, 'O'); // 주변을 다시 확인하기
                    if (!isPNear) { // 만약 주변이 false라면 false 리턴하고 끝
                        return false;
                    }
                }
            }
        }
        return true;
    }
}