[2021 카카오 인턴십]거리두기 확인하기

📍 문제 설명

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

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

 

💡 접근

거리 1부터2까지 다른 응시자를 만나게 되면 거리두기가 안되고 있는 것이다.

bfs 이용해서 거리가 2일 때까지 확인해서 풀이할 수도 있겠다!

 

 

👩‍💻 코드

import java.io.*;
import java.util.*;

public class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        Arrays.fill(answer, 1);
        boolean[][] visited;
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};

        //i번째 대기실
        for(int i = 0; i < 5; i++) {
            visited = new boolean[5][5];
            for(int j = 0; j < 5; j++) {
                //응시자가 없는 행은 거리두기 확인 안해도 된다.
                if(!places[i][j].contains("P")) continue;
                //응시자가 있으면 멘헤튼 거리확인
                for(int k = 0; k < 5; k++) {
                    if(places[i][j].charAt(k) == 'P' && !visited[j][k]) {
                        visited[j][k] = true;
                        System.out.println(j + ", " + k + " 지점에 응시자 발견!");
                        //여기서 거리두기 제대로 확인해보기.
                        //1.상하좌우를 일단 가본다. 벽이면 그 지역은 더 안봐도 된다. 응시자가 있으면 바로 끝낸다.
                        for(int l = 0; l < 4; l++) {
                            int nx = j + dx[l];
                            int ny = k + dy[l];
                            if(nx<0 || ny<0 || nx>=5 || ny>=5 || visited[nx][ny]) continue;
                            if(places[i][nx].charAt(ny) == 'P') {
                                answer[i] = 0;
                                break;
                            }
                            if(places[i][nx].charAt(ny) == 'O') {
                                //2.빈 테이블에 왔다. 이 지역에서도 상하좌우 확인해본다.
                                for(int m = 0; m < 4; m++) {
                                    int nnx = nx + dx[m];
                                    int nny = ny + dy[m];
                                    if(nnx<0 || nny<0 || nnx>=5 || nny>=5 || visited[nnx][nny]) continue;
                                    if(places[i][nnx].charAt(nny) == 'P') {
                                        answer[i] = 0;
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            System.out.println();
        }
        System.out.println(Arrays.toString(answer));
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Solution s = new Solution();
        s.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"}});
    }


    private class Point {
        private int x;
        private int y;

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