[프로그래머스] [Level2] 거리두기 확인하기 JAVA

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

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

[풀이]

2차원 map을 만들어서 P 와 P 사이의 거리가 2이하인 것을 발견하는 문제이다.
입력받은 값 중에 P가 있으면 그 좌표를 큐에 담아 bfs를 통해 다른 P를 발견하면 종료 하는 식으로 하면된다.

그럼 P가 움직일수 있는 경우는 첫 시작에서 2번움직여서 탐색하면 되는데..
여기서 굳이 두번탐색 하지 않고도 , 입력받은 map 값 자체를 P가 아닌것을 P로 바꾸기만 하면
한번 탐색만으로도 충분히 발견할 수 있다.

이게 무슨말이냐면 만약
POP 가 있다고 가정을 하자. 그럼 맨 앞에 P에서 출발한다고 가정했을때 O가 있으므로 , O=>P로 바꾸면
PPP가 된다.
이제 두번째 P에서 출발을 한다고 했을때 , 바로 앞에 P가 있으므로 false를 return 하면 된다는 뜻.

다른예시로 POOP 가정을 하면
첫번째 P가 움직여서 => PPOP
두번째 P가 움직여서 => PPPP
둘이 만나지 않기때문에 true를 반환.

이런식으로 입력받은 P의 좌표를 한번 탐색만으로 검사를 끝낼 수 있다.  

 
import java.util.*;
import java.io.*;
import java.util.stream.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Solution sol = new Solution();
        String[][] places = {{"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"}};
        sol.solution(places);
    }
}
 
class Solution {
    int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};
    public int[] solution(String[][] places) {
 
        String[][] map = new String[5][5];
        List<Integer> answer = new ArrayList<>();
        for (String[] in : places) {
            Queue<int[]> q = new LinkedList<>();
            for(int i=0;i<5;i++) {
                map[i] = in[i].split("");
 
                for(int j=0;j<map[i].length;j++)
                    if(map[i][j].equals("P")) q.add(new int[]{j,i});
            }
            answer.add(check(map, q));
        }
        return answer.stream()
                .mapToInt(Integer::intValue).toArray();
    }
 
    private int check(String[][] map, Queue<int[]> q) {
 
        while(!q.isEmpty()){
            int[] cur = q.poll();
 
            for(int i=0;i<dx.length;i++){
 
                int nextX = dx[i]+cur[0];
                int nextY = dy[i]+cur[1];
 
                if(!isRange(nextX,nextY)) continue;
 
                if(map[nextY][nextX].equals("P")) return 0;
                else if(map[nextY][nextX].equals("O")) map[nextY][nextX]="P";
            }
        }
        return 1;
    }
 
    private boolean isRange(int x, int y) {
        return x>=0&&y>=0&&x<5&&y<5;
    }
 
}