2021 카카오 채용연계형 인턴십 거리두기 확인하기

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

문제를 보고 bfs 로 너비 탐색을 하면서 풀면 되겠다 싶었다.
배열을 순회하면서 해당 값이 사람(P) 인 경우에만 bfs 메서드를 실행하게 한다.
핵심 코드는 bfs 메서드라 해당 부분만 설명하자면 아래와 같다.

// 상, 하, 좌, 우 탐색
private static final int[] X_DIR = {-1, 1, 0, 0};
private static final int[] Y_DIR = {0, 0, -1, 1};

private final String PERSON = "P";
private final String PARTITION = "X";

...

private boolean bfs(int x, int y, String[][] placesOfRoom) {
    boolean[][] visited = new boolean[placesOfRoom.length][placesOfRoom[0].length];
    Queue<Point> queue = new LinkedList<>();
    queue.add(new Point(x, y));
    visited[x][y] = true;
    while (!queue.isEmpty()) {
        Point point = queue.poll();
        for (int i = 0; i < 4; i++) {
            int nextX = point.getX() + X_DIR[i];
            int nextY = point.getY() + Y_DIR[i];
            // 범위를 넘어가는가
            if (nextX < 0 || nextY < 0 || nextX >= placesOfRoom.length || nextY >= placesOfRoom[0].length
                continue;
            }
            // 거리두기를 만족하는가
            int manhattan = Math.abs(x - nextX) + Math.abs(y - nextY);
            if (manhattan > 2) {
                continue;
            }
            // 이미 방문했는가
            if (visited[nextX][nextY]) {
                continue;
            }
            visited[nextX][nextY] = true;
            String place = placesOfRoom[nextX][nextY];
            // 파티션인가
            if (place.equals(PARTITION)) {
                continue;
            }
            // 사람인가
            if (place.equals(PERSON)) {
                return false;
            }
            queue.add(new Point(nextX, nextY));
        }
    }
    return true;
}

Queue 에 넣고 bfs 탐색을 하면 되는데,
상, 하, 좌, 우 순으로 체크하면서 배열 범위를 넘어가는지 체크한다.
그 후 맨해튼 거리를 구해서 거리가 3을 넘어간다면 정상적인 거리두기 이므로 넘어간다.
해당 부분 아래 부터는 거리두기를 만족하지 않는 위치라는 의미이므로,
만약 사람이 있다면 false 를 반환하여 result 배열에 0 을 담으면 된다.
(각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return)

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {

    private static final int[] X_DIR = {-1, 1, 0, 0};
    private static final int[] Y_DIR = {0, 0, -1, 1};
    private final String PERSON = "P";
    private final String PARTITION = "X";

    public int[] solution(String[][] places) {
        List<Integer> answer = new ArrayList<>();

        for (String[] place : places) {
            String[][] placesOfRoom = toSplit(place);
            int valid = isValidDir(placesOfRoom) ? 1 : 0;
            answer.add(valid);
        }

        return answer.stream()
                     .mapToInt(Integer::intValue)
                     .toArray();
    }

    private String[][] toSplit(String[] place) {
        String[][] result = new String[place.length][place[0].length()];
        for (int i = 0; i < place.length; i++) {
            result[i] = place[i].split("");
        }
        return result;
    }

    private boolean isValidDir(String[][] placesOfRoom) {
        for (int i = 0; i < placesOfRoom.length; i++) {
            for (int j = 0; j < placesOfRoom[0].length; j++) {
                if (placesOfRoom[i][j].equals(PERSON)) {
                    if (!bfs(i, j, placesOfRoom)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private boolean bfs(int x, int y, String[][] placesOfRoom) {
        boolean[][] visited = new boolean[placesOfRoom.length][placesOfRoom[0].length];
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = point.getX() + X_DIR[i];
                int nextY = point.getY() + Y_DIR[i];

                // 범위를 넘어가는가
                if (nextX < 0 || nextY < 0 || nextX >= placesOfRoom.length || nextY >= placesOfRoom[0].length) {
                    continue;
                }

                // 거리두기를 만족하는가
                int manhattan = Math.abs(x - nextX) + Math.abs(y - nextY);
                if (manhattan > 2) {
                    continue;
                }

                // 이미 방문했는가
                if (visited[nextX][nextY]) {
                    continue;
                }

                visited[nextX][nextY] = true;
                String place = placesOfRoom[nextX][nextY];
                // 파티션인가
                if (place.equals(PARTITION)) {
                    continue;
                }

                // 사람인가
                if (place.equals(PERSON)) {
                    return false;
                }

                queue.add(new Point(nextX, nextY));
            }
        }
        return true;
    }
}

class Point {

    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

회고

처음에 맨해튼 거리 체크를 next 위치가 사람인 경우에만 체크하게 했더니 세 번째 대기실 예제에서 틀렸다..
(2, 2) 위치의 사람과 (4, 2) 위치의 사람의 맨해튼 거리가 2로 나오다보니 틀린것..
사람인지 체크하기 전에 맨해튼을 먼저 체크하게 된다면 (2, 2) 와 (3, 4) 비교에서 걸리게 되므로 종료된다.
따라서 정상적으로 통과가 됨.
다 풀어놓고 이 부분에서 막혀서 좀 아쉽긴했다..ㅠ