[프로그래머스 Level2] 거리두기 확인하기(JAVA) - 2021 카카오 인턴

 

문제

---

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

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

해당 문제의 내용이 길어 생략했습니다.

 

 

 

 

문제풀이

---

해당 그림이 제일 큰 힌트를 주었습니다.

 

• 참가자 사이의 거리가 2가 되더라도 X로 막혀있을 경우 거리두기를 지킨 것이고, 파티션을 사이에 두고 앉은 경우도 지킨 것이 됩니다. 
• 세번째 그림은 참가자 사이의 거리가 2이고 빈테이블이 있어 거리두기를 지키지 못했습니다.
• 이를 토대로 결국 도달할 수 있는가 없는가로 생각하여, 상하좌우로 움직이는 BFS로 문제를 풀 수 있다는 사실을 알았습니다.
• 또한 문제의 제한이 5라는 매우작은 수로 모든 테이블마다 참가자를 BFS탐색해도 시간초과가 나지 않겠다 라고 생각을 했습니다.
• 이제 문제의 조건대로 구현만 하면 됩니다.

 

 

 

소스코드

---

import java.util.*;

class Solution {

    static final int dx[] = {0, 0, 1, -1};
    static final int dy[] = {1, -1, 0, 0};
    static int[][] check;
    static char[][] map;
    static int n = 5;
    static class Node{
        int x;
        int y;

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

    public int[] solution(String[][] places) {
        int[] answer = new int[n];

        int i = 0;
        for (String[] place : places) {
            answer[i] = func(place);
            i++;
        }

        return answer;
    }


    static int func(String[] place) {
        check = new int[n][n];
        map = new char[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = place[i].charAt(j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 'P') {
                    if (!bfs(i, j)) {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }

    static boolean bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        check = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(check[i], -1);
        }

        q.add(new Node(x, y));
        check[x][y] = 0;

        while (!q.isEmpty()) {
            Node now = q.poll();
            x = now.x;
            y = now.y;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (map[nx][ny] != 'X' && check[nx][ny] == -1) {
                        check[nx][ny] = check[x][y] + 1;
                        if (map[nx][ny] == 'P' && check[nx][ny] <= 2) {
                            return false;
                        }
                        q.add(new Node(nx, ny));
                    }
                }
            }
        }

        return true;
    }
}