[프로그래머스][Java][Lv. 2] 거리두기 확인하기

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    HashMap<String, String> nodeMap;
    
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        for (int i = 0; i < places.length; i++) {
            answer[i] = 1;
            String[] roomArr = places[i];
            nodeMap = new HashMap<>();
            ArrayList<String> pList = new ArrayList<>();

            for (int y = 0; y < 5; y++) {
                for (int x = 0; x < 5; x++) {
                    String yx = y + "" + x;
                    String subStr = roomArr[y].substring(x, x + 1);
                    nodeMap.put(yx, subStr);
                    if (subStr.equals("P")) pList.add(yx);
                }
            }
            for (String pYx : pList) answer[i] = Math.min(answer[i], check(pYx));
        }
        return answer;
    }
    
    private int check(String pYx) {
        Integer yx = Integer.parseInt(pYx);
        Integer y = yx / 10, x = yx % 10;
        StringBuilder result = new StringBuilder();
        int[][] checkArr = new int[][] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 },  // 상하좌우
                                         { 1, 0, 1, 0 }, { 1, 0, 0, -1 }, { 1, 0, 0, 1 },  // 상
                                         { -1, 0, -1, 0 }, { -1, 0, 0, -1 }, { -1, 0, 0, 1 },  // 하
                                         { 0, -1, 1, 0 }, { 0, -1, -1, 0 }, { 0, -1, 0, -1 },  // 좌
                                         { 0, 1, 1, 0 }, { 0, 1, -1, 0 }, { 0, 1, 0, 1 } };  // 우
        
        for (int i = 0; i < checkArr.length; i++) {
            result.setLength(0);
            result.append("P");
            int tempY = y, tempX = x;
            for (int j = 0; j < checkArr[i].length; j += 2) {
                tempY += checkArr[i][j];
                tempX += checkArr[i][j + 1];
                result.append(nodeMap.getOrDefault(String.valueOf(tempY + "" + tempX), ""));
            }
            String strResult = result.toString();
            if (strResult.equals("PP") || strResult.equals("POP")) return 0;
        }
        return 1;
    }
}

 

---

 

후기

맨해튼 거리가 뭔가 했는데 밑에 설명이 나와있었다. 그냥 단순히 움직인 거리라고 생각하면 될 것 같다. 맨해튼 거리가 2 이하인 경우, 거리 두기를 해야 하므로 ㄱ자 ㄴ자 아니면 ㅡ 3칸인 경우 P끼리 붙어 있거나 테이블인 O를 끼고 있는 경우만 거리 두기를 지키지 않은 상태이다. 해당 경우는 PP와 POP(꺾여있는거를 폈다고 생각하면)밖에 없다. 그렇기 때문에 해당 경우가 있으면 0을 반환하면 된다. 나는 각 대기실마다 P인 경우만 리스트에 담아서 P의 주위만 살펴보는 모든 경우의 수를 찾았다. 2칸(바로 옆에 붙어 있는 경우), 3칸(POP, PXP, PPP와 같은 경우)로 나눠서 가능한 경우를 checkArr에 담아서 순회하며 조건을 검사했다.

제출하고 다른 사람 풀이를 보니 BFS로 푼 풀이도 있었다. 나중에 시간이 나면 BFS로도 풀어봐야겠다.