[PG] 2021 카카오 채용연계 > 거리두기 확인하기

2021. 10. 10. 16:04알고리즘/프로그래머스 문제 풀이

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

접근 방법

BFS로 간단하게 구현해주면 되는 문제이다.

주의 사항

Need Know

  1. BFS

전체 코드 ( Java )

import java.util.*;
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        for(int i=0; i<places.length; i++){
            boolean isOk = true;
            loop : for(int k=0; k< 5; k++){
                for(int z=0; z<5; z++){
                    char edge = places[i][k].charAt(z);
                    // 거리두기 2 이하 여야함 아니면 파티션은 ㅇㅋ
                    if(edge == 'P'){
                        boolean[][] visited = new boolean[5][5];
                        Queue<Point> queue = new LinkedList<>();
                        queue.add(new Point(k,z,0));
                        visited[k][z] = true;
                        while(!queue.isEmpty()){
                            Point now = queue.poll();
                            for(int p = 0; p<4; p++){
                                int nx = now.x+dx[p];
                                int ny = now.y+dy[p];
                                if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
                                if(visited[nx][ny] || now.distance == 2) continue;
                                if(places[i][nx].charAt(ny) == 'O'){
                                    queue.add(new Point(nx,ny,now.distance+1));
                                    visited[nx][ny] = true;
                                }
                                if(places[i][nx].charAt(ny) == 'P'){
                                    if(now.distance + 1 <= 2){
                                        isOk = false;
                                        break loop;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            if(isOk){
                answer[i] = 1;
            }else{
                answer[i] = 0;
            }
        }
        return answer;
    }

            // }
}
class Point{
    int x,y,distance;

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