[programmers] 2021 카카오 채용연계형 인턴십 > 거리두기 확인하기

import java.util.*;
class Solution {
    public int[] solution(String[][] places) {
        int[] answer = {};
        int N = 5;
        answer = new int[N];
        Arrays.fill(answer, 1);
        boolean flag = false;
        
        
        for(int t=0;t<places.length;t++){
            flag = false;
            System.out.println("t = " + t);
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(places[t][i].charAt(j) == 'P'){
                        for(int x=0;x<N;x++){
                            for(int y=0;y<N;y++){
                                if(i == x && j == y) continue;
                                if(places[t][x].charAt(y) == 'P' && (Math.abs(i - x) + Math.abs(j - y)) <= 2){
                                    if(i==x){
                                        int mid = (j+y)/2;
                                        if(places[t][x].charAt(mid) == 'X') continue;
                                    } else if(j==y){
                                        int mid = (i+x)/2;
                                        if(places[t][mid].charAt(y) == 'X') continue;
                                    } 
                                    else if(places[t][i].charAt(y) == 'X' && places[t][x].charAt(j) == 'X') continue;
                                                            System.out.println("places[t][i].charAt(j)" + t + ", " + i + ", " + j);
                                                 System.out.println("places[t][x].charAt(y)" + t + ", " + x + ", " + y);

                                    flag = true;
                                    answer[t] = 0;
                                    break;
                                }
                                if(flag) break;
                            }
                            if(flag) break;
                        }    
                    }
                    if(flag) break;
                }
                if(flag) break;
            }
        }
        
        
        
        return answer;
    }
}

 

ㅋㅋㅋ 테스트 케이스 제외하면 4중 for문.. 이러고 싶지 않았는데 ... 풀면서도 뭔가 웃겼다. 정확성 테스트가 10초길래 구현으로 막 풀어봤더니 정답이네 .. !

 

BFS 로 다시 풀어봐야겠다!

import java.util.*;
class Solution {
    static class Info {
        int x, y, dist;
        Info(int x, int y, int dist){this.x = x; this.y = y; this.dist = dist;}
    }
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, -1, 0, 1};
    static int N = 5;
    public int[] solution(String[][] places) {
        int[] answer = {};
        answer = new int[N];
        Arrays.fill(answer, 1);
       
        for(int t=0;t<N;t++){
            Queue<Info> q = new LinkedList<>();
            boolean flag = false;
            boolean visited[][] = new boolean[N][N];
            for(int x=0;x<N;x++){
                for(int y=0;y<N;y++){
                    if(places[t][y].charAt(x) == 'P'){
                        q.offer(new Info(x, y, 0));
                        visited[y][x] = true;
                    }
                    
                    if(bfs(q, visited, places, t) == 0){
                        answer[t] = 0;
                        break;
                    }
                }
            }
           
        } // testcase
        
        return answer;
    }
    
    static int bfs(Queue<Info> q, boolean visited[][], String[][] places, int t){   
        while(!q.isEmpty()){
            Info cur = q.poll();
            for(int k=0;k<4;k++){
                int ny = cur.y + dy[k];
                int nx = cur.x + dx[k];
                int nd = cur.dist + 1;
                
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[ny][nx] || nd > 2) continue;
                 System.out.println("ny = " + ny + " nx = " + nx + " nd = " + nd + " -> " + places[t][ny].charAt(nx) );
               
                if(places[t][ny].charAt(nx) == 'P') return 0;
                if(places[t][ny].charAt(nx) == 'O'){
                    q.offer(new Info(nx, ny, nd));
                    visited[ny][nx] = true;
                }
            }
        }
        
        return 1;
    }
}