[Programmers] 거리두기 확인하기 (Java, Kotlin)

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

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

문제

5개의 대기실은 각 5 X 5 크기를 가집니다. 응시자들이 앉아있을 때 맨해튼 거리가 2이하로 앉은 경우는 거리두기가 잘 지켜지지 않는 것을 의미합니다. 이때 모든 강의실에 대해서 거리두기가 잘 지켜지고 있다면 1, 그렇지 않다면 0을 반환하면 됩니다.

 

접근 아이디어

1. 반복문을 통해 5개 대기실을 모두 확인해야 합니다.

2. 일반적인 BFS 알고리즘을 이용하여 각 지원자의 지점으로 부터 맨해튼 거리가 2이하인 지점들을 모두 확인합니다.

3. 거리두기가 잘 지켜지고 있다면 1, 그렇지 않다면 0을 반환합니다.

 

조심해야할 점

이미 대기실에서 거리두기가 잘 지켜지고 있지 않다면 바로 끝내버리는 것이 효율성 측면에서 좋습니다.

 

- Java

import java.util.*;

class Solution {
    static boolean[][] visit = new boolean[5][5];
    static int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        for (int index = 0; index < places.length; index++) {
            String[] place = places[index];
            char[][] arr = new char[5][5];
            for (int i = 0; i < place.length; i++) {
                for (int j = 0; j < place[i].length(); j++) {
                    arr[i][j] = place[i].charAt(j);
                }
            }

            answer[index] = bfs(arr);
        }
        return answer;
    }

    public int bfs(char[][] arr) {
        //응시자 기지점 모두 찾
        List<Point> pList = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (arr[i][j] == 'P') pList.add(new Point(i, j, 0));
            }
        }

        //모든 응시자에 대해서 잘 앉아있나 확인하기
        boolean check = false;
        Loop: for (Point p : pList) {
            Queue<Point> queue = new LinkedList<>();
            for(int i=0; i<5; i++) Arrays.fill(visit[i], false);
            queue.add(new Point(p.x, p.y, p.dir));
            visit[p.x][p.y] = true;
            
            while(!queue.isEmpty()) {
                Point now = queue.poll();
                if (now.dir > 2) continue;

                for (int[] dir : dirs) {
                    int nextX = now.x + dir[0];
                    int nextY = now.y + dir[1];

                    if (nextX < 0 || nextY < 0 || nextX >= 5 || nextY >= 5) continue; //범위내에 없으면 패스
                    if (arr[nextX][nextY] == 'X') continue; //파티션인 상태는 패스
                    if (visit[nextX][nextY]) continue; //방문된 곳 패스

                    if (now.dir + 1 <= 2 && arr[nextX][nextY] == 'P') {
                        check = true;
                        break Loop;
                    }

                    visit[nextX][nextY] = true;
                    queue.add(new Point(nextX, nextY, now.dir + 1));
                }
            }
        }

        return check ? 0 : 1;
    }

    static class Point {
        int x;
        int y;
        int dir;

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

 

 

- Kotlin

import java.util.*;

class Solution {
    val dirs = arrayOf(
        arrayOf(0, 1),
        arrayOf(1, 0),
        arrayOf(0, -1),
        arrayOf(-1, 0)
    )

    fun solution(places: Array<Array<String>>): IntArray {
        var answer = IntArray(places.size)
        for(index in places.indices) {
            val arr = Array(5) { CharArray(5) }
            for (i in places[index].indices) {
                for(j in places[index][i].indices) {
                    arr[i][j] = places[index][i][j]
                }
            }

            answer[index] = bfs(arr)
        }

        return answer
    }

    fun bfs(arr: Array<CharArray>): Int {
        //응시자 지점 모두 찾기
        val pList = ArrayList<Point>()
        for (i in arr.indices) {
            for(j in arr[i].indices) {
                if(arr[i][j] == 'P') pList.add(Point(i, j, 0))
            }
        }

        //모든 응시자에 대해서 잘 앉아있나 확인하기
        var check = false
        for(p in pList) {
            val queue = LinkedList<Point>()
            val visit = Array(5) { BooleanArray(5) }
            queue.add(Point(p.x, p.y, p.dir))
            visit[p.x][p.y] = true

            while(!queue.isEmpty()) {
                val now = queue.poll()
                if(now.dir > 2) continue
                for(dir in dirs) {
                    val nextX = now.x + dir[0]
                    val nextY = now.y + dir[1]

                    if(nextX < 0 || nextY < 0 || nextX >= 5 || nextY >= 5) continue //범위내에 없으면 패스
                    if(arr[nextX][nextY] == 'X') continue //파티션인 상태는 패스
                    if(visit[nextX][nextY]) continue //방문된 곳 패스

                    if(now.dir + 1 <= 2 && arr[nextX][nextY] == 'P') {
                        check = true
                        break
                    }
                    visit[nextX][nextY] = true
                    queue.add(Point(nextX, nextY, now.dir + 1))
                }

                if(check) break
            }

            if(check) break
        }

        return if(check) 0 else 1
    }

    class Point (
        var x: Int,
        var y: Int,
        var dir: Int
    )
}

 

 

좌(Java 채점 결과), 우(Kotlin 채점 결과)