[JAVA][Programmers] 거리두기 확인하기

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

프로그래머스

여담

글을 쓰는 방식을 좀 바꿨다.

바꾼지 좀 되긴 했는데 원래는 뭘 쓸지 고민하고 어떤 구성으로 쓸지, 문제 풀이가 올바른 풀이인지 다 결정한 뒤에 썼는데

블로그에 글 올리는 부담감을 좀 줄이고 싶어서 그냥 문제를 풀면서 동시에 글도 쓰고 틀리면 틀린대로 다 적는

일기형식으로 바꿨더니 글쓰기가 편해졌다.

다른 사람들이 보기엔 좀 지저분하고 난잡해보일 수 있긴하지만

뭐 어차피 내 블로그 많이 보러오는 것도 아니고

못 할 말을 쓰는 것도 아니니깐..

일기처럼 내가 이 문제를 푸는 과정에서 뭐가 문제였고 이런 모든것을 기록하려고 한다.

---

풀이 과정

규칙이 뭔가 좀 있는데 사실 뜯어보면 쉬운 문제인 것 같다

코테를 계속 풀다보니 뇌가 컴퓨터처럼 변한건가 모르겠지만

메모장에 쓴 코드 구현 방법
1. P(사람)를 만나면 주변을 확인하는데 거리를 기록해야 된다.(조건2 때문)

2. 거리가 1이고, 

• 'O'이면 해당 주변을 탐색한다. 주변을 탐색하는 과정으로 넘어갈 때 거리+1 증가 시켜주기. (테이블 이므로 맨해튼 거리 2에 사람이 있는지 봐야함.)
• 'X'면 파티션이니깐 통과
• 'P'면 바로 옆에 사람이라는 뜻 -> 탈락

3. 거리가 2이고

• 'P'이면 실패 (조건2를 달성하지 못함)

정리를 해보면 P일때 주변 탐색을 시작하는데, 탐색하는 동안 P를 발견하면 안된다.
따라서 P가 발견되면 바로 false를 리턴해주고,
X일 경우엔 이동할 수 없으니 그냥 패스

O일 경우엔 탐색을 해야하는데

로직상 P를 만나면 그 주변을 Queue에 넣는게 아니라
P를 만나면 그 P를 Queue에 넣고 시작하므로 
== 'O' -> 탐색이 아니라

!= 'X' -> 이때 탐색을 해야된다.(왜냐하면 0일때도 Queue에 들어가기 때문. 이 때도 4방향 탐색을 해줘야한다.)

 

그대로 구현을 해보면

import java.util.LinkedList;
import java.util.Queue;

public class PG_81302 {
    private static int[] dr = {-1, 1, 0, 0};
    private static int[] dc = {0, 0, -1, 1};
    private static int N = 5;

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

        for (int t = 0; t < places.length; t++) {
            if (isValidPlace(places[t])) {
                answer[t] = 1;
            } else {
                answer[t] = 0;
            }
        }

        return answer;
    }

    private boolean isValidPlace(String[] place) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (place[r].charAt(c) == 'P') {
                    if (!check(place, r, c)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    private boolean check(String[] place, int r, int c) {
        boolean[][] visited = new boolean[N][N];
        visited[r][c] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c, 0});

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int cr = poll[0];
            int cc = poll[1];
            int dist = poll[2];

            // 주변 탐색 시 사람이면
            if (dist >= 1 && place[cr].charAt(cc) == 'P') {
                return false;
            }

            if (dist < 2) {
                for (int i = 0; i < 4; i++) {
                    int nr = cr + dr[i];
                    int nc = cc + dc[i];

                    if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc]) {
                        if (place[nr].charAt(nc) != 'X') {
                            visited[nr][nc] = true;
                            queue.add(new int[]{nr, nc, dist + 1});
                        }
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        PG_81302 solution = new PG_81302();
        String[][] places = {{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
        int[] solution1 = solution.solution(places);
        for (int i = 0; i < solution1.length; i++) {
            System.out.print(solution1[i] + " ");
        }
        System.out.println();
    }
}

---

문제 이해 자체는 쉬웠지만 이를 코드로 나타내는게 간단한 문제는 아니었다.

각종 조건을 어떻게 하면 깔끔하고 이쁘게 작성할 수 있을까 많이 고민했던 문제.
처음에는 if문을 구구절절 썼는데 위의 코드는 디버깅하면서 정리하고 또 정리한 결과이다.

 

21년 카카오 채용연계형 인턴십 기출 문제인데

문제가 간단한 것을 보면 이 사람이 코드를 얼마나 깔끔하게 짜는지 스타일을 본 것 같기도 하다.

내가 시험시간에 이 문제를 만났으면 이렇게 깔끔하게 작성할 수 있었을까?

 

프로그래머스 문제는 메소드를 나누어 구현하는 연습하기에 좋은 문제들이 많아서 좋다.

그리고 많이 고민하고 노력하면 풀리는 문제가 많아서 코딩테스트 연습하기엔 프로그래머스가 좋고

각종 알고리즘이나 수학 지식등을 공부하기엔 백준이 좀 더 좋은 것 같다.

백준을 풀다보면 '오~~ 이런 것도 있네' 이러면서 풀게 된다.

 

뭐 어쨌든 둘 다 공부하기엔 좋다는거..