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

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

프로그래머스

문제 설명

이런 배열이 주어지면 

이런 2차원 배열이 생기고 위 조건을 만족하는지 따져봐야 합니다. P와 P의 거리가 맨해튼 거리 2 이하인지 찾고 만약 2보다 크면 거리두기를 만족한 것입니다.  2보다 작은데 사이에 X가 없으면 거리두기를 만족하지 못한 것이므로 거리두기를 만족하지 못한 것 입니다.

 

문제에 대한 아이디어

import java.util.ArrayList;
class Node{
    int x; int y;
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Solution {
    char [][] pro;
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i =0; i<places.length; ++i){
            pro = new char[5][5];
            for(int j=0; j<5; ++j){
                pro[j] = places[i][j].toCharArray();
            }
            answer[i]= sol();
        }
        return answer;
    }
    public int sol(){
        ArrayList<Node> arr = new ArrayList<>();
        for(int i = 0; i<5; ++i){
            for(int j =0; j <5; ++j){
                if(pro[i][j] == 'P'){
                    arr.add(new Node(j,i));
                }
            }
        } 
        boolean ch = true;
        for(int i =0; i< arr.size()-1; ++i){
            for(int j = 1; j<arr.size(); ++j){
                if(Math.abs(arr.get(i).x - arr.get(j).x) + Math.abs(arr.get(i).y - arr.get(j).y) == 1){
                    ch = false;
                    break;
                }
                if(Math.abs(arr.get(i).x - arr.get(j).x) + Math.abs(arr.get(i).y - arr.get(j).y) == 2){
                    if(check(arr.get(i).x, arr.get(i).y, arr.get(j).x, arr.get(j).y) == false){
                        ch= false;
                        break;
                   }
                }
            }
        }
        if(ch == true) return 1;
        else return 0;
    }
    public boolean check(int ax, int ay, int bx, int by){
        if(ax == bx){
            if(Math.abs(ay-by)==1) return false;
            if(ay > by) {
                if(pro[ay-1][ax] == 'X') return true;
                else return false;
            }
            else{
                if(pro[ay+1][ax] == 'X') return true;
                else return false;
            }
        }
        else if(ay == by){
            if(Math.abs(ax-bx)==1) return false;
            if(ax > bx){
                 if(pro[ay][ax-1] == 'X') return true;
                else return false;
            }else{
                 if(pro[ay][ax+1] == 'X') return true;
                else return false;
            }
        }
        else{
            if(ax > bx && ay > by){
                if(pro[ay][ax-1] == 'X' && pro[ay-1][ax] == 'X') return true;
                else return false;
            } 
            if(ax > bx && ay < by){
                if(pro[ay][ax-1] == 'X' && pro[ay+1][ax] == 'X') return true;
                else return false;
            }
            if(ax < bx && ay > by){
                 if(pro[ay-1][ax] == 'X' && pro[ay][ax+1] == 'X') return true;
                else return false;
            }
            if(ax < bx && ay < by){
                 if(pro[ay][ax+1] == 'X' && pro[ay+1][ax] == 'X') return true;
                else return false;
            }
        }
        return true;
    }
}

사실 이 문제는 옛날에 한 번 풀어봤던 문제입니다. 

• 그때는 P의 모든 좌표를 찾은 다음에 그 좌표와 좌표 사이의 맨해튼 거리를 계산 후 사이 거리 판별
• 맨해튼 거리가 2 이하이면 그 좌표들 사이의 X가 있는지 검사

이렇게 반복적인 코드와 가독성이 낮은 코드 였습니다. 

 

이 책에서는 저번에 배운 4방향 거리를 사용하여 훨씬 쉽고 가독성이 좋은 방법으로 코드를 짜서 다시 공부해봤습니다.

 

책에 있는 가독성 좋은 방법

• 현재 자신이 P일 때만 검사를 시작하면 됩니다.
• P일 때 상하좌우 방향을 탐색합니다. 
  • P이면 거리두기를 실행 X
  • O이면 또 한번 상하좌우를 탐색합니다. 단 자신이 왔던 방향은 탐색하면 안됩니다. 
  • X이면 파티션이 있는 것이므로 넘어갑니다.

class Solution {
    //위, 왼쪽, 오른쪽, 아래
    private static final int dx[] = {0, -1, 1, 0};
    private static final int dy[] = {1, 0, 0 , -1};
        
    private boolean isVolunteer(char[][] room, int y, int x, int no){
        for(int d = 0; d < 4; ++d){
            if(d == no) continue;
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) continue;
            if(room[ny][nx] == 'P') return true;
        }
        return false;
    }
        
    private boolean isDistanced(char[][] room, int y, int x){
        for(int d = 0; d < 4; ++d){
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) continue;
            switch(room[ny][nx]){
                case 'P' : return false;
                case 'O' : 
                    if(isVolunteer(room, ny, nx, 3-d)) return false;
                    break;
            }
        }
        return true;
    }
    
    private boolean isDistanced(char[][] room){
        for(int y = 0; y < room.length; ++y){
            for(int x = 0; x <room[y].length; ++x){
                if(room[y][x] != 'P') continue;
                if(!isDistanced(room, y, x)) return false; 
            }
        }
        return true;
    }
    
    public int[] solution(String[][] places) {
        int [] answer = new int[5];
        for(int i = 0; i < places.length; ++i){
            String[] place = places[i];
            char[][] room = new char[place.length][];
            for(int j = 0; j < room.length; ++j){
                room[j] = place[j].toCharArray();
            }
            if(isDistanced(room)){
                answer[i] = 1;
            }
            else{
                answer[i] = 0;
            }
        } 
        return answer;
    }
}

isDistanced라는 이름의 메소드가 2개 존재합니다. 하지만 2개의 매개변수가 다르기 때문에 메소드를 2개 모두 사용할 수 있습니다. 

• Solution에서는 String[]으로 받은 5개의 String을 모두 char[][]로 바꿔줍니다.
• isDistanced(char[][] room)
  • 모든 2차원 배열을 돌면서 P인지 검사합니다.
  • P이면 다른 메소드를 실행합니다.
• isDistanced(char[][] room, int y, int x)
  • 현재 자신의 좌표가 P인 경우입니다.
  • 이때 상하좌우로 탐색하면서 P일 경우 거리두기 실패
  • O일 경우 그 O인 좌표를 상하좌우 탐색합니다.
• isVolunteer(char[][] room, int y, int x, int no)
  • O인 경우 실행하는 메소드로 상하좌우가 P인 경우는 거리두기 실패입니다.
  • 이때 상하좌우 중 자신이 왔던 방향은 제외해야 합니다.