[Java] 프로그래머스 (거리두기 확인하기) Level 2

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

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

 

Approach

Greedy 한 BFS 문제이다.

2021 카카오 채용연계형 인턴십 문제이다.

 

문제에서 언급하는 맨해튼 거리는 자기 자신 기준 거리가 2인 마름모 꼴만 검사하면 된다. 나머지 부분은 볼 필요가 없다.

따라서 P인 부분들을 기준으로 거리가 2인 마름모 꼴을 검사하여, 그 범위 안에 또다른 P가 존재하는지 찾으면 된다.

본인은 (i, j) 기준 상하좌우 점을 모두 검사하여 P일 경우 그대로 flag 를 true로 만들면서 종료하였고, O(빈 테이블)일 경우 Queue에 추가하여 한번더 상하좌우 점을 검사하였다.

 

Code

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.ArrayDeque;
import java.util.Queue;

public class CheckDistancing {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static String[][] places;
    static char[][] map;
    static boolean flag;

    public int[] solution(String[][] places) {
        int[] ans = new int[5];
        map = new char[5][5];
        for (int i = 0; i < places.length; i++) {
            for (int j = 0; j < 5; j++) {
                map[j] = places[i][j].toCharArray();
            }

            flag = false;

            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    if (!flag && map[j][k] == 'P') {
                        bfs(j, k);
                    }
                }
            }
            ans[i] = flag ? 0 : 1;
        }
        return ans;
    }

    static void bfs(int sx, int sy) {
        Queue<Point> q = new ArrayDeque<>();

        for (int i = 0; i < 4; i++) {
            int nx = sx + dx[i];
            int ny = sy + dy[i];

            if (inRange(nx, ny)) {
                if (map[nx][ny] == 'P') {
                    flag = true;
                    return;
                }

                if (map[nx][ny] != 'X') {
                    q.offer(new Point(nx, ny));
                }
            }
        }

        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if (nx == sx && ny == sy) {
                    continue;
                }

                if (inRange(nx, ny)) {
                    if (map[nx][ny] == 'P') {
                        flag = true;
                        break;
                    }
                }
            }
        }
    }

    static boolean inRange(int x, int y) {
        if (x >= 0 && x < 5 && y >= 0 && y < 5) {
            return true;
        }
        return false;
    }

    static class Point{
        int x, y;

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

    @Test
    void test() {
        Assertions.assertArrayEquals(new int[]{1, 0, 1, 1, 1}
                , solution(new String[][]{{"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"}}));
    }
}