[알고리즘] 프로그래머스 거리두기 확인하기 (2021 카카오 채용연계형 인턴십) -BFS- 자바, 코틀린

 

https://programmers.co.kr/learn/courses/30/lessons/81302?language=kotlin 

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

 

 

 

요즘 할일이 많아 블로그랑 개인 공부를 2주 넘게 못한거 같네요 ㅠ 

정말 오랜만에 프로그래머스  거리두기 확인하기라는 BFS 유형의 문제를 풀어봤습니다 ㅎㅎ

문제 이름 그대로 대기실에 있는 사람들이 거리두기를 지켰는지 확인하는 문제입니다.

대기실에 책상(통로), 사람, 파티션(벽)이 있는데 사람이 2칸 내에 있으면 거리두기를 안지킨겁니다. (책상은 통로라고 생각하시면 됩니다.) 

 

문제 접근은 빨리 했는데 코드 양이 조금 있어서 시간은 조금은 걸렸네요 ㅎㅎ 아니면 오랜만에 풀어서 뇌가 굳은건지;;

 

풀이방법을 요약하자면,

1. 대기실 공간을 탐색하기위해 BFS 사용

2. Point에 좌표외에 사람과의 2칸내 여부를 알기 위한 cnt 변수 추가, 그래서 사람이 있는 곳인 경우 처음에 cnt를 2로 초기화 해줍니다. 한칸씩 이동할때는 cnt-1 을 해주고요

가 핵심이고 나머지는 기본 BFS 문제와 유사하게 풀이하면 됩니다. !

 

주석으로 풀이를 추가해놨습니다. 다음과 같습니다.

 

[Java]

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    private int[] answer;
    private char[][] map = new char[5][5];
    private boolean[][] isVisited = new boolean[5][5];
    private int[] dr = {-1, 0, 1, 0};
    private int[] dc = {0, -1, 0, 1};

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.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"}});
    }

    public int[] solution(String[][] places) {
        answer = new int[places.length];
        Arrays.fill(answer, 1); // 1로 초기화
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                String str = places[i][j];
                for (int k = 0; k < str.length(); k++) {
                    map[j][k] = str.charAt(k);
                }
            }
            for (int r = 0; r < 5; r++) {
                boolean flag = true; // 거리두기 지켰는지
                for (int c = 0; c < 5; c++) {
                    // 초기화
                    isVisited = new boolean[5][5];
                    if (map[r][c] != 'X') { //벽아닌곳
                        if (!bfs(r, c, i)) { // 방 거리두기 잘 지키는지 탐색
                            flag = false;
                            break; // 거리두기 안지킴 -> 탐색중지
                        }
                    }
                }
                if (!flag) break; // 거리두기 안지킴 -> 탐색중지
            }
        }
        for (int i = 0; i < 5; i++) { // 정답 세팅
            System.out.println(answer[i]);
        }
        return answer;
    }

    private boolean bfs(int r, int c, int index) {
        Queue<Point> queue = new LinkedList<>();
        if (isPerson(r, c)) {
            queue.offer(new Point(r, c, 2));
        } else {
            queue.offer(new Point(r, c, 0));
        }
        isVisited[r][c] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if ((r2 >= 0 && r2 < 5 && c2 >= 0 && c2 < 5) && !isVisited[r2][c2] && map[r2][c2] != 'X') { //방문안하고 벽아닌곳
                    // 거리두기 여부 체크
                    if (isPerson(r2, c2) && point.cnt > 0) {
                        answer[index] = 0; // 거리두기 실패
                        return false; // 거리두기 실패
                    }
                    // BFS 탐색 추가
                    if (isPerson(r2, c2)) { // 사람있는 곳
                        queue.offer(new Point(r2, c2, 2));
                    } else { // 사람없는 곳
                        queue.offer(new Point(r2, c2, point.cnt - 1));
                    }
                    isVisited[r2][c2] = true;
                }
            }
        }
        return true; // 거리두기 지킴
    }

    // 사람이 앉은 자리인지
    private boolean isPerson(int r, int c) {
        return map[r][c] == 'P';
    }

    class Point {
        int r;
        int c;
        int cnt; //  사람과의 거리

        public Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            if (cnt < 0) { // 마이너스 된 경우 0으로 세팅해줌
                this.cnt = 0;
            } else {
                this.cnt = cnt;
            }
        }
    }

}

 

[Kotlin]

import java.util.*

internal class Solution {
    private lateinit var answer: IntArray
    private val map = Array(5) { CharArray(5) }
    private var isVisited = Array(5) { BooleanArray(5) }
    private val dr = intArrayOf(-1, 0, 1, 0)
    private val dc = intArrayOf(0, -1, 0, 1)
    fun solution(places: Array<Array<String>>): IntArray {
        answer = IntArray(places.size)
        Arrays.fill(answer, 1) // 1로 초기화
        for (i in 0..4) {
            for (j in 0..4) {
                val str = places[i][j]
                for (k in str.indices) {
                    map[j][k] = str[k]
                }
            }
            for (r in 0..4) {
                var flag = true // 거리두기 지켰는지
                for (c in 0..4) { // 초기화
                    isVisited = Array(5) { BooleanArray(5) }
                    if (map[r][c] != 'X') { //벽아닌곳
                        if (!bfs(r, c, i)) { // 방 거리두기 잘 지키는지 탐색
                            flag = false
                            break // 거리두기 안지킴 -> 탐색중지
                        }
                    }
                }
                if (!flag) break // 거리두기 안지킴 -> 탐색중지
            }
        }
        for (i in 0..4) { // 정답 세팅
            println(answer[i])
        }
        return answer
    }

    private fun bfs(r: Int, c: Int, index: Int): Boolean {
        val queue: Queue<Point> = LinkedList()
        if (isPerson(r, c)) {
            queue.offer(Point(r, c, 2))
        } else {
            queue.offer(Point(r, c, 0))
        }
        isVisited[r][c] = true
        while (queue.isNotEmpty()) {
            val point = queue.poll()
            for (i in 0..3) {
                val r2 = point.r + dr[i]
                val c2 = point.c + dc[i]
                if (r2 in 0..4 && c2 in 0..4 && !isVisited[r2][c2] && map[r2][c2] != 'X') { //방문안하고 벽아닌곳
// 거리두기 여부 체크
                    if (isPerson(r2, c2) && point.cnt > 0) {
                        answer[index] = 0 // 거리두기 실패
                        return false // 거리두기 실패
                    }
                    // BFS 탐색 추가
                    if (isPerson(r2, c2)) { // 사람있는 곳
                        queue.offer(Point(r2, c2, 2))
                    } else { // 사람없는 곳
                        queue.offer(Point(r2, c2, point.cnt - 1))
                    }
                    isVisited[r2][c2] = true
                }
            }
        }
        return true // 거리두기 지킴
    }

    // 사람이 앉은 자리인지
    private fun isPerson(r: Int, c: Int): Boolean = map[r][c] == 'P'

    internal inner class Point(var r: Int, var c: Int, cnt: Int) {
        var cnt //  사람과의 거리
                = 0

        init {
            if (cnt < 0) { // 마이너스 된 경우 0으로 세팅해줌
                this.cnt = 0
            } else {
                this.cnt = cnt
            }
        }
    }

    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            val solution = Solution()
            solution.solution(arrayOf(arrayOf("POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"), arrayOf("POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"), arrayOf(
                    "PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"), arrayOf("OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"), arrayOf(
                    "PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP")))
        }
    }
}

https://github.com/mtjin/algorithm_practice/commit/b783a96eb2a5a7bb2c5715ff96343d3263d4229d

프로그래머스 거리두기 확인하기 풀이 · mtjin/algorithm_practice@b783a96

 

 

코로나 시기에 어울리는 BFS문제였습니다. 얼른 코로나가 끝났으면 좋겠네여~

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!