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

 

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

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

본 문제는 2021 카카오 채용연계 인턴십에서 출제된 문제이며, BFS 응용 문제이다.

제약 사항으로는 주어진 문자열에서는 'X' 는 방문이 불가하며, 맨하탄 거리 2 이하인 거리에 Player 가 존재할 경우 거리두기가 실패한 케이스이며, 해당 쿼리에 대한 결과로 0을 출력한다. 정상적으로 거리두기가 성공한 경우에는 1을 출력한다.

예제 코드는 아래와 같습니다.

 

import java.util.*;
class Point {
    int y;
    int x;
    int depth;
    public Point(int y, int x, int depth) {
        this.y = y;
        this.x = x;
        this.depth = depth;
    }
}

class Solution {
    static int[] dy = {0,1,0,-1};
    static int[] dx = {1,0,-1,0};
    public static int[] solution(String[][] places) {
        int[] answer = {};
        List<Integer> answerList = new ArrayList<>();
        for (int i = 0; i < places.length; i++) {
            List<Integer> pList = new ArrayList<>();
            int result = 1;
            for (int j = 0; j < places[i].length; j++) {
                for (int k = 0; k < 5; k++) {
                    if (places[i][j].charAt(k) == 'P') {
                        pList.add(j * 5 + k);
                    }
                }
            }
            for (int j = 0; j < pList.size(); j++) {
                if (result == 0) break;
                boolean[][] check = new boolean[5][5];
                Queue<Point> q = new LinkedList<>();
                int cur_y = pList.get(j) / 5;
                int cur_x = pList.get(j) % 5;
                q.add(new Point(cur_y,cur_x,0));
                check[cur_y][cur_x] = true;
                while(!q.isEmpty()) {
                    Point pos = q.poll();
                    if (places[i][pos.y].charAt(pos.x) == 'P' && pos.depth > 0 && pos.depth <= 2) {
                        result = 0;
                        break;
                    }
                    for (int d = 0; d < 4; d++) {
                        int ny = pos.y + dy[d];
                        int nx = pos.x + dx[d];
                        if (ny >= 0 && ny < 5 && nx >= 0 && nx < 5 && check[ny][nx] == false && places[i][ny].charAt(nx) != 'X') {
                            q.add(new Point(ny,nx,pos.depth+1));
                            check[ny][nx] = true;
                        }
                    }
                }
            }
            answerList.add(result);
        }
        return answerList.stream().mapToInt(e -> e).toArray();
    }
}